 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 4 no. 2
1. The First-Order Theory of Ordering Constraints over Feature Trees
The system FT< of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate the first-order theory of FT< and its fragments in detail, both over finite trees and over possibly infinite trees. We prove that the first-order theory of FT< is undecidable, in contrast to the first-order theory of FT which is well-known to be decidable. We show that the entailment problem of FT< with existential quantification is PSPACE-complete. So far, this problem has been shown decidable, coNP-hard in case of finite trees, PSPACE-hard in case of arbitrary trees, and cubic time when restricted to quantifier-free entailment judgments. To show PSPACE-completeness, we show that the entailment problem of FT< with existential quantification is equivalent to the inclusion problem of non-deterministic finite automata. Available at http://www.ps.uni-saarland.de/Publications/documents/FTSubTheory_98.pdf
2. Oriented Multicast Routing Applied to Network Level Agent Search
Many protocols need a discovery mechanism to enable a given node to locate one or several nodes involved in the same communication. However, there is no protocol ready to fulfill this service at the network-layer. Every protocol usually implements its own solution. In particular, multicast protocols often use a searching technique based on an algorithm called expanding ring search. This algorithm searches for nodes in all directions and thus uses much bandwidth. However a typical search can usually restrict its scan in a specific direction. To enable this broadcast restriction, we propose an oriented multicast routing algorithm. The algorithm's principle is to direct the multicast of packets towards a special node, involved in the communication, in order to search only in a limited area. The area must be as small as possible to reduce network flooding but still has to contain many nodes satisfying the search criteria. This new algorithm is the core part of a network-level node search framework also defined herein. A search protocol based on this framework could provide a network-level agent discovery service to current protocols. We have simulated an agent search with our algorithm on one side and with the expanding ring algorithm on the other side and we give comparative results.
3. Linear time recognition of P4-indifference graphs
A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a
4. A permutations representation that knows what "Eulerian" means
Eulerian numbers (and ''Alternate Eulerian numbers'') are often interpreted as distributions of statistics defined over the Symmetric group. The main purpose of this paper is to define a way to represent permutations that provides some other combinatorial interpretations of these numbers. This representation uses a one-to-one correspondence between permutations and the so-called \emphsubexceedant functions.
5. P_4-Colorings and P_4-Bipartite Graphs
A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4). Examples of P_4-free 2-colorable graphs (also called P_4-bipartite graphs) include parity graphs and graphs with ''few'' P_4s like P_4-reducible and P_4-sparse graphs. We prove that, given k≥ 2, \emphP_4-Free k-Colorability is NP-complete even for comparability graphs, and for P_5-free graphs. We then discuss the recognition, perfection and the Strong Perfect Graph Conjecture (SPGC) for P_4-bipartite graphs with special P_4-structure. In particular, we show that the SPGC is true for P_4-bipartite graphs with one P_3-free color class meeting every P_4 at a midpoint.
6. Analysis of Transmissions Scheduling with Packet Fragmentation
We investigate a scheduling problem in which packets, or datagrams, may be fragmented. While there are a few applications to scheduling with datagram fragmentation, our model of the problem is derived from a scheduling problem present in data over CATV networks. In the scheduling problem datagrams of variable lengths must be assigned (packed) into fixed length time slots. One of the capabilities of the system is the ability to break a datagram into several fragments. When a datagram is fragmented, extra bits are added to the original datagram to enable the reassembly of all the fragments. We convert the scheduling problem into the problem of bin packing with item fragmentation, which we define in the following way: we are asked to pack a list of items into a minimum number of unit capacity bins. Each item may be fragmented in which case overhead units are added to the size of every fragment. The cost associated with fragmentation renders the problem NP-hard, therefore an approximation algorithm is needed. We define a version of the well-known Next-Fit algorithm, capable of fragmenting items, and investigate its performance. We present both worst case and average case results and compare them to the case where fragmentation is not allowed.
7. Minimum Eccentricity Multicast Trees
We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the \emphminimum eccentricity multicast tree problem, and is directly related to the quality of service requirements of real multipoint applications. We deal directly with the problem in its general form, meaning that the sets of source and sink nodes need not be overlapping nor disjoint. The main contribution of this work is a polynomial algorithm for this problem on general networks which is inspired by an innovative method that uses geometric relationships on the xy-plane.
8. Defect Effect of Bi-infinite Words in the Two-element Case
Let X be a two-element set of words over a finite alphabet. If a bi-infinite word possesses two X-factorizations which are not shiftequivalent, then the primitive roots of the words in X are conjugates. Note, that this is a strict sharpening of a defect theorem for bi-infinite words stated in \emphKMP. Moreover, we prove that there is at most one bi-infinite word possessing two different X-factorizations and give a necessary and sufficient conditions on X for the existence of such a word. Finally, we prove that the family of sets X for which such a word exists is parameterizable.
9. Simple Equational Specifications of Rational Arithmetic
We exhibit an initial specification of the rational numbers equipped with addition, subtraction, multiplication, greatest integer function, and absolute value. Our specification uses only the sort of rational numbers. It uses one hidden function; that function is unary. But it does not use an error constant, or extra (hidden) sorts, or conditional equations. All of our work is elementary and self-contained.
10. Asymptotic normality of recursive algorithms via martingale difference arrays
We propose martingale central limit theorems as an tool to prove asymptotic normality of the costs of certain recursive algorithms which are subjected to random input data. The recursive algorithms that we have in mind are such that if input data of size N produce random costs L_N, then L_N=^D L_n+ L_N-n+R_N for N ≥ n_0≥ 2, where n follows a certain distribution P_N on the integers \0, \ldots ,N\ and L_k =^D L_k for k≥ 0. L_n, L_N-n and R_N are independent, conditional on n, and R_N are random variables, which may also depend on n, corresponding to the cost of splitting the input data of size N (into subsets of size n and N-n) and combining the results of the recursive calls to yield the overall result. We construct a martingale difference array with rows converging to Z_N:= [L_N - E L_N] / [√Var L_N]. Under certain compatibility assumptions on the sequence (P_N)_N≥ 0 we show that a pair of sufficient conditions (of Lyapunov type) for Z_N → ^DN(0,1) can be restated as a pair of conditions regarding asymptotic relations between three sequences. All these sequences satisfy the same type of linear equation, that is also the defining equation for the sequence (E L_N)_N≥ 0 and thus very likely a well studied object. In the case that the P_N are binomial distributions with the same parameter p, and for deterministic R_N, we demonstrate the power of this approach. We derive very general sufficient conditions in terms of the sequence (R_N)_N≥ 0 (and for the scale […]
11. On a hierarchy of Boolean functions hard to compute in constant depth
Any attempt to find connections between mathematical properties and complexity has a strong relevance to the field of Complexity Theory. This is due to the lack of mathematical techniques to prove lower bounds for general models of computation.\par This work represents a step in this direction: we define a combinatorial property that makes Boolean functions ''\emphhard'' to compute in constant depth and show how the harmonic analysis on the hypercube can be applied to derive new lower bounds on the size complexity of previously unclassified Boolean functions.
12. A note on representations of the finite Heisenberg group and sums of greatest common divisors
We review an elementary approach to the construction of all irreducible representations of the finite Heisenberg group. Determining the number of inequivalent classes of irreducible representations by different methods leads to an identity of sums involving greatest common divisors. We show how this identity can be generalized and derive an explicit formula for the sums.
13. Cubic Cayley graphs with small diameter.
In this paper we apply Polya's Theorem to the problem of enumerating Cayley graphs on permutation groups up to isomorphisms induced by conjugacy in the symmetric group. We report the results of a search of all three-regular Cayley graphs on permutation groups of degree at most nine for small diameter graphs. We explore several methods of constructing covering graphs of these Cayley graphs. Examples of large graphs with small diameter are obtained.
14. Paths of specified length in random k-partite graphs
Fix positive integers k and l. Consider a random k-partite graph on n vertices obtained by partitioning the vertex set into V_i, (i=1, \ldots,k) each having size Ω (n) and choosing each possible edge with probability p. Consider any vertex x in any V_i and any vertex y. We show that the expected number of simple paths of even length l between x and y differ significantly depending on whether y belongs to the same V_i (as x does) or not. A similar phenomenon occurs when l is odd. This result holds even when k,l vary slowly with n. This fact has implications to coloring random graphs. The proof is based on establishing bijections between sets of paths.
15. Finite Automata with Generalized Acceptance Criteria
We examine the power of nondeterministic finite automata with acceptance of an input word defined by a leaf language, i.e., a condition on the sequence of leaves in the automaton's computation tree. We study leaf languages either taken from one of the classes of the Chomsky hierarchy, or taken from a time- or space-bounded complexity class. We contrast the obtained results with those known for leaf languages for Turing machines and Boolean circuits.
16. Benders decomposition for local access network design with two technologies
We have worked with the local access network design problem with two cable technologies. This is an optimization problem in graphs that consists of linking an origin node to a set of terminal nodes which have a flow demand. There are also a set of Steiner or transshipment nodes which do not have demand. Each arc of the graph has two associated costs: a variable cost depending on the flow through the arc and a fixed cost associated with the installation of the arc. Moreover, in each arc we can install one of two available technologies: optical fiber or copper (we can also use radio links with any other cable technology). Each one of these technologies has different variable and fixed costs. To be more precise, the fixed cost of the optical fiber is greater than that of the copper, but its variable cost is much smaller. The problem was modeled using a multicommodity flow formulation in which we added some structural constraints. This model was used to apply the Benders decomposition method. The structural constraints have the objective of trying to guarantee that the master problem of the Benders decomposition will yield a tree. The Benders subproblems are trivial network flow problems. The dual variables have commodity meaningfull values and are evaluated in a systematic form. The algorithm was implemented in C++ with CPLEX 3.0 callable library. We have tested the algorithm with some test instances obtained by a generator of problems that we developed.
17. A Degree-Decreasing Lemma for (MOD_q-MOD_p) Circuits
Consider a (MOD_q,MOD_p) circuit, where the inputs of the bottom MOD_p gates are degree-d polynomials with integer coefficients of the input variables (p, q are different primes). Using our main tool ―- the Degree Decreasing Lemma ―- we show that this circuit can be converted to a (MOD_q,MOD_p) circuit with \emphlinear polynomials on the input-level with the price of increasing the size of the circuit. This result has numerous consequences: for the Constant Degree Hypothesis of Barrington, Straubing and Thérien, and generalizing the lower bound results of Yan and Parberry, Krause and Waack, and Krause and Pudlák. Perhaps the most important application is an exponential lower bound for the size of (MOD_q,MOD_p) circuits computing the n fan-in AND, where the input of each MOD_p gate at the bottom is an \empharbitrary integer valued function of cn variables (c<1) plus an arbitrary linear function of n input variables.
18. An Approximate L^p Difference Algorithm for Massive Data Streams
Several recent papers have shown how to approximate the difference ∑ _i|a_i-b_i| or ∑ |a_i-b_i|^2 between two functions, when the function values a_i and b_i are given in a data stream, and their order is chosen by an adversary. These algorithms use little space (much less than would be needed to store the entire stream) and little time to process each item in the stream. They approximate with small relative error. Using different techniques, we show how to approximate the L^p-difference ∑ _i|a_i-b_i|^p for any rational-valued p∈(0,2], with comparable efficiency and error. We also show how to approximate ∑ _i|a_i-b_i|^p for larger values of p but with a worse error guarantee. Our results fill in gaps left by recent work, by providing an algorithm that is precisely tunable for the application at hand. These results can be used to assess the difference between two chronologically or physically separated massive data sets, making one quick pass over each data set, without buffering the data or requiring the data source to pause. For example, one can use our techniques to judge whether the traffic on two remote network routers are similar without requiring either router to transmit a copy of its traffic. A web search engine could use such algorithms to construct a library of small ''sketches,'' one for each distinct page on the web; one can approximate the extent to which new web pages duplicate old ones by comparing the sketches of the web pages. […]
19. An Efficient Algorithm for the Maximum Distance Problem
Efficient algorithms for temporal reasoning are essential in knowledge-based systems. This is central in many areas of Artificial Intelligence including scheduling, planning, plan recognition, and natural language understanding. As such, scalability is a crucial consideration in temporal reasoning. While reasoning in the interval algebra is NP-complete, reasoning in the less expressive point algebra is tractable. In this paper, we explore an extension to the work of Gerevini and Schubert which is based on the point algebra. In their seminal framework, temporal relations are expressed as a directed acyclic graph partitioned into chains and supported by a \emphmetagraph data structure, where time points or events are represented by vertices, and directed edges are labelled with < or ≤ . They are interested in fast algorithms for determining the strongest relation between two events. They begin by developing fast algorithms for the case where all points lie on a chain. In this paper, we are interested in a generalization of this, namely we consider the problem of finding the maximum ''distance'' between two vertices in a \emphchain; this problem arises in real world applications such as in process control and crew scheduling. We describe an O(n) time preprocessing algorithm for the maximum distance problem on chains. It allows queries for the maximum number of < edges between two vertices to be answered in O(1) time. This matches the performance of […]
20. The topological entropy of iterated piecewise affine maps is uncomputable
We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise affine function in dimension four. The same result holds for saturated linear functions in unbounded dimension. We ask whether the topological entropy of a piecewise affine function is always a computable real number, and conversely whether every non-negative computable real number can be obtained as the topological entropy of a piecewise affine function. It seems that these two questions are also open for cellular automata.
21. Overlap-free symmetric D0L words
A D0L word on an alphabet Σ =\0,1,\ldots,q-1\ is called symmetric if it is a fixed point w=\varphi(w) of a morphism \varphi:Σ ^* → Σ ^* defined by \varphi(i)=øverlinet_1 + i øverlinet_2 + i\ldots øverlinet_m + i for some word t_1t_2\ldots t_m (equal to \varphi(0)) and every i ∈ Σ ; here øverlinea means a \bmod q. We prove a result conjectured by J. Shallit: if all the symbols in \varphi(0) are distinct (i.e., if t_i ≠q t_j for i ≠q j), then the symmetric D0L word w is overlap-free, i.e., contains no factor of the form axaxa for any x ∈ Σ ^* and a ∈ Σ .