OpenRaiser/Intern-Atlas huggingface dataset:
Stable normal forms for polynomial system solving
Venue: arXiv cs.SC 2008
Year: 2008

This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT'05]. This general border basis algorithm weakens the monomial ordering requirement for \grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.
An Integrated Software-based Solution for Modular and Self-independent Networked Robot
Venue: arXiv cs.RO 2008
Year: 2008

An integrated software-based solution for a modular and self-independent networked robot is introduced. The wirelessly operatable robot has been developed mainly for autonomous monitoring works with full control over web. The integrated software solution covers three components : a) the digital signal processing unit for data retrieval and monitoring system; b) the externally executable codes for control system; and c) the web programming for interfacing the end-users with the robot. It is argued that this integrated software-based approach is crucial to realize a flexible, modular and low development cost mobile monitoring apparatus.
Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems
Venue: arXiv cs.CC 2008
Year: 2008

We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}. For a class F of boolean functions and a class G of graphs, an (F,G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and G contains all planar graphs, then it is #P-complete to compute the number of fixed points in an (F,G)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas.
The Capacity Region of the Cognitive Z-interference Channel with One Noiseless Component
Venue: arXiv cs.IT 2008
Year: 2008

We study the discrete memoryless Z-interference channel (ZIC) where the transmitter of the pair that suffers from interference is cognitive. We first provide upper and lower bounds on the capacity of this channel. We then show that, when the channel of the transmitter-receiver pair that does not face interference is noiseless, the two bounds coincide and therefore yield the capacity region. The obtained results imply that, unlike in the Gaussian cognitive ZIC, in the considered channel superposition encoding at the non-cognitive transmitter as well as Gel'fand-Pinsker encoding at the cognitive transmitter are needed in order to minimize the impact of interference. As a byproduct of the obtained capacity region, we obtain the capacity result for a generalized Gel'fand-Pinsker problem.
Probabilistic reasoning with answer sets
Venue: arXiv cs.AI 2008
Year: 2008

This paper develops a declarative language, P-log, that combines logical and probabilistic arguments in its reasoning. Answer Set Prolog is used as the logical foundation, while causal Bayes nets serve as a probabilistic foundation. We give several non-trivial examples and illustrate the use of P-log for knowledge representation and updating of knowledge. We argue that our approach to updates is more appealing than existing approaches. We give sufficiency conditions for the coherency of P-log programs and show that Bayes nets can be easily mapped to coherent P-log programs.
Fully distributed and fault tolerant task management based on diffusions
Venue: arXiv cs.DC 2008
Year: 2008

The task management is a critical component for the computational grids. The aim is to assign tasks on nodes according to a global scheduling policy and a view of local resources of nodes. A peer-to-peer approach for the task management involves a better scalability for the grid and a higher fault tolerance. But some mechanisms have to be proposed to avoid the computation of replicated tasks that can reduce the efficiency and increase the load of nodes. In the same way, these mechanisms have to limit the number of exchanged messages to avoid the overload of the network. In a previous paper, we have proposed two methods for the task management called active and passive. These methods are based on a random walk: they are fully distributed and fault tolerant. Each node owns a local tasks states set updated thanks to a random walk and each node is in charge of the local assignment. Here, we propose three methods to improve the efficiency of the active method. These new methods are based on a circulating word. The nodes local tasks states sets are updated thanks to periodical diffusions along trees built from the circulating word. Particularly, we show that these methods increase the efficiency of the active method: they produce less replicated tasks. These three methods are also fully distributed and fault tolerant. On the other way, the circulating word can be exploited for other applications like the resources management or the nodes synchronization.
Network Protection Codes: Providing Self-healing in Autonomic Networks Using Network Coding
Venue: arXiv cs.NI 2008
Year: 2008

Agile recovery from link failures in autonomic communication networks is essential to increase robustness, accessibility, and reliability of data transmission. However, this must be done with the least amount of protection resources, while using simple management plane functionality. Recently, network coding has been proposed as a solution to provide agile and cost efficient network self-healing against link failures, in a manner that does not require data rerouting, packet retransmission, or failure localization, hence leading to simple control and management planes. To achieve this, separate paths have to be provisioned to carry encoded packets, hence requiring either the addition of extra links, or reserving some of the resources for this purpose. In this paper we introduce autonomic self-healing strategies for autonomic networks in order to protect against link failures. The strategies are based on network coding and reduced capacity, which is a technique that we call network protection codes (NPC). In these strategies, an autonomic network is able to provide self-healing from various network failures affecting network operation. The techniques improve service and enhance reliability of autonomic communication. Network protection codes are extended to provide self-healing from multiple link failures in autonomic networks. We provide implementation aspects of the proposed strategies. We present bounds and network protection code constructions. Finally, we study the construction of such codes over the binary field. The paper also develops an Integer Linear Program formulation to evaluate the cost of provisioning connections using the proposed strategies.
An analysis of a random algorithm for estimating all the matchings
Venue: arXiv cs.GR 2008
Year: 2008

Counting the number of all the matchings on a bipartite graph has been transformed into calculating the permanent of a matrix obtained from the extended bipartite graph by Yan Huo, and Rasmussen presents a simple approach (RM) to approximate the permanent, which just yields a critical ratio O($nω(n)$) for almost all the 0-1 matrices, provided it's a simple promising practical way to compute this #P-complete problem. In this paper, the performance of this method will be shown when it's applied to compute all the matchings based on that transformation. The critical ratio will be proved to be very large with a certain probability, owning an increasing factor larger than any polynomial of $n$ even in the sense for almost all the 0-1 matrices. Hence, RM fails to work well when counting all the matchings via computing the permanent of the matrix. In other words, we must carefully utilize the known methods of estimating the permanent to count all the matchings through that transformation.
The Impact of New Technologies in Public Financial Management and Performance: Agenda for Public Financial Management Reformance in the Context of Global Best Practices
Venue: arXiv cs.OH 2008
Year: 2008

Information and Communication Technologies (ICT) has practically penetrated into all spheres of life. Therefore a closer look at the impact of ICT in public financial management and performance is highly justified. Public finance is defined as a field of economics concerned with paying for collective or governmental activities, and with the administration and design of those activities. Activities will be viewed as services or more precisely as public services. We believe that there is need to consider performance from the perspective of effective performance and the perceived performance. In fact the real or effective performance might not correspond to the perceived performance. A service can be considered from the perspective of the decision-maker, who in our case could be a government or a collectivity. ICT can be employed in the three phases that concern the decision-maker: design, implementation and evaluation. The beneficiaries of a service can employ ICT in any of the three phases - awareness, exploitation and assessment - for guarantying a high level of efficiency. Each phase in the environment of a service will be presented as well as illustrations of how ICT can be employed in order to improve the end-result of each one of them. We believe that a high efficiency of each phase will produce a high global efficiency. It should be noted however that the effectiveness of any system is highly dependent on the human engagement in the system. Therefore, the impact of ICT in public financial management will be felt only if the decision-makers and the end-users of the services engage themselves in the success of the system. Instead of giving a catalog of services, the focus has been on the model (or methodology) to adopt in designing services for which ICT could enhance the implementation.
Logic programs with propositional connectives and aggregates
Venue: arXiv cs.AI 2008
Year: 2008

Answer set programming (ASP) is a logic programming paradigm that can be used to solve complex combinatorial search problems. Aggregates are an ASP construct that plays an important role in many applications. Defining a satisfactory semantics of aggregates turned out to be a difficult problem, and in this paper we propose a new approach, based on an analogy between aggregates and propositional connectives. First, we extend the definition of an answer set/stable model to cover arbitrary propositional theories; then we define aggregates on top of them both as primitive constructs and as abbreviations for formulas. Our definition of an aggregate combines expressiveness and simplicity, and it inherits many theorems about programs with nested expressions, such as theorems about strong equivalence and splitting.
To Cooperate, or Not to Cooperate in Imperfectly-Known Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, communication over imperfectly-known fading channels with different degrees of cooperation is studied. The three-node relay channel is considered. It is assumed that communication starts with the network training phase in which the receivers estimate the fading coefficients of their respective channels. In the data transmission phase, amplify-and-forward and decode-and-forward relaying schemes are employed. For different cooperation protocols, achievable rate expressions are obtained. These achievable rate expressions are then used to find the optimal resource allocation strategies. In particular, the fraction of total time or bandwidth that needs to be allocated to the relay for best performance is identified. Under a total power constraint, optimal allocation of power between the source and relay is investigated. Finally, bit energy requirements in the low-power regime are studied.
Accelerated Data-Flow Analysis
Venue: arXiv cs.DS 2008
Year: 2008

Acceleration in symbolic verification consists in computing the exact effect of some control-flow loops in order to speed up the iterative fix-point computation of reachable states. Even if no termination guarantee is provided in theory, successful results were obtained in practice by different tools implementing this framework. In this paper, the acceleration framework is extended to data-flow analysis. Compared to a classical widening/narrowing-based abstract interpretation, the loss of precision is controlled here by the choice of the abstract domain and does not depend on the way the abstract value is computed. Our approach is geared towards precision, but we don't loose efficiency on the way. Indeed, we provide a cubic-time acceleration-based algorithm for solving interval constraints with full multiplication.
A Separation Algorithm for Improved LP-Decoding of Linear Block Codes
Venue: arXiv cs.IT 2008
Year: 2008

Maximum Likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an Integer Programming (IP) problem. Feldman et al. relaxed this IP problem and presented Linear Programming (LP) based decoding algorithm for linear block codes. In this paper, we propose a new IP formulation of the ML decoding problem and solve the IP with generic methods. The formulation uses indicator variables to detect violated parity checks. We derive Gomory cuts from our formulation and use them in a separation algorithm to find ML codewords. We further propose an efficient method of finding cuts induced by redundant parity checks (RPC). Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. We demonstrate on two LDPC codes and one BCH code that our separation algorithm performs significantly better than LP decoding.
Standard Logics Are Valuation-Nonmonotonic
Venue: arXiv cs.LO 2008
Year: 2008

It has recently been discovered that both quantum and classical propositional logics can be modelled by classes of non-orthomodular and thus non-distributive lattices that properly contain standard orthomodular and Boolean classes, respectively. In this paper we prove that these logics are complete even for those classes of the former lattices from which the standard orthomodular lattices and Boolean algebras are excluded. We also show that neither quantum nor classical computers can be founded on the latter models. It follows that logics are "valuation-nonmonotonic" in the sense that their possible models (corresponding to their possible hardware implementations) and the valuations for them drastically change when we add new conditions to their defining conditions. These valuations can even be completely separated by putting them into disjoint lattice classes by a technique presented in the paper.
Asteroids in rooted and directed path graphs
Venue: arXiv cs.DM 2008
Year: 2008

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.
The Korrontea Data Modeling
Venue: arXiv cs.MM 2008
Year: 2008

Needs of multimedia systems evolved due to the evolution of their architecture which is now distributed into heterogeneous contexts. A critical issue lies in the fact that they handle, process, and transmit multimedia data. This data integrates several properties which should be considered since it holds a considerable part of its semantics, for instance the lips synchronization in a video. In this paper, we focus on the definition of a model as a basic abstraction for describing and modeling media in multimedia systems by taking into account their properties. This model will be used in software architecture in order to handle data in efficient way. The provided model is an interesting solution for the integration of media into applications; we propose to consider and to handle them in a uniform way. This model is proposed with synchronization policies to ensure synchronous transport of media. Therefore, we use it in a component model that we develop for the design and deployment of distributed multimedia systems.
Beyond Bandlimited Sampling: Nonlinearities, Smoothness and Sparsity
Venue: arXiv cs.IT 2008
Year: 2008

Sampling theory has benefited from a surge of research in recent years, due in part to the intense research in wavelet theory and the connections made between the two fields. In this survey we present several extensions of the Shannon theorem, that have been developed primarily in the past two decades, which treat a wide class of input signals as well as nonideal sampling and nonlinear distortions. This framework is based on viewing sampling in a broader sense of projection onto appropriate subspaces, and then choosing the subspaces to yield interesting new possibilities. For example, our results can be used to uniformly sample non-bandlimited signals, and to perfectly compensate for nonlinear effects.
Comparison of Binary Classification Based on Signed Distance Functions with Support Vector Machines
Venue: arXiv cs.LG 2008
Year: 2008

We investigate the performance of a simple signed distance function (SDF) based method by direct comparison with standard SVM packages, as well as K-nearest neighbor and RBFN methods. We present experimental results comparing the SDF approach with other classifiers on both synthetic geometric problems and five benchmark clinical microarray data sets. On both geometric problems and microarray data sets, the non-optimized SDF based classifiers perform just as well or slightly better than well-developed, standard SVM methods. These results demonstrate the potential accuracy of SDF-based methods on some types of problems.
A New Method for Knowledge Representation in Expert System's (XMLKR)
Venue: arXiv cs.DC 2008
Year: 2008

Knowledge representation it is an essential section of a Expert Systems, Because in this section we have a framework to establish an expert system then we can modeling and use by this to design an expert system. Many method it is exist for knowledge representation but each method have problems, in this paper we introduce a new method of object oriented by XML language as XMLKR to knowledge representation, and we want to discuss advantage and disadvantage of this method.
Optimal Relay-Subset Selection and Time-Allocation in Decode-and-Forward Cooperative Networks
Venue: arXiv cs.IT 2008
Year: 2008

We present the optimal relay-subset selection and transmission-time for a decode-and-forward, half-duplex cooperative network of arbitrary size. The resource allocation is obtained by maximizing over the rates obtained for each possible subset of active relays, and the unique time allocation for each set can be obtained by solving a linear system of equations. We also present a simple recursive algorithm for the optimization problem which reduces the computational load of finding the required matrix inverses, and reduces the number of required iterations. Our results, in terms of outage rate, confirm the benefit of adding potential relays to a small network and the diminishing marginal returns for a larger network. We also show that optimizing over the channel resources ensures that more relays are active over a larger SNR range, and that linear network constellations significantly outperform grid constellations. Through simulations, the optimization is shown to be robust to node numbering.
The Plane-Width of Graphs
Venue: arXiv cs.DM 2008
Year: 2008

Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane. We also investigate how plane-width behaves under various operations, such as homomorphism, disjoint union, complement, and the Cartesian product.
An $O(k^{3} log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
Venue: arXiv cs.DS 2008
Year: 2008

In the Survivable Network Design problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with a connectivity requirement $r(u,v)$ for each pair $u,v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges, that satisfies the given set of pairwise connectivity requirements. In the edge-connectivity version we need to ensure that there are $r(u,v)$ edge-disjoint paths for every pair $u, v$ of vertices, while in the vertex-connectivity version the paths are required to be vertex-disjoint. The edge-connectivity version of SNDP is known to have a 2-approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem. We present an extremely simple algorithm to achieve an $O(k^3 \log n)$-approximation for this problem, where $k$ denotes the maximum connectivity requirement, and $n$ denotes the number of vertices. We also give a simple proof of the recently discovered $O(k^2 \log n)$-approximation result for the single-source version of vertex-connectivity SNDP. We note that in both cases, our analysis in fact yields slightly better guarantees in that the $\log n$ term in the approximation guarantee can be replaced with a $\log τ$ term where $τ$ denotes the number of distinct vertices that participate in one or more pairs with a positive connectivity requirement.