Abstract: It was proved by [Garey and Johnson, 1983] that computing the crossing number of a graph is an NP-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is NP-hard to determine the crossing number of a simple cubic graph. In particular, this implies that the minor-monotone version of crossing number is also NP-hard, which has been open till now.
Abstract: This paper continues the algebraic theory of Ésik, Kuich on semiring-semimodule pairs and quemirings that is applicable to languages that contain finite and infinite words. The main advantage is that we get rid of the idempotency assumption for the semimodule needed at several places. Additionally, we consider linear systems as a generalization of rightlinear grammars. Moreover, we develop an algorithm that constructs, for a given finite automaton, an equivalent one without $\epsilon$-moves.
Abstract: We define new, both model-theoretical and fixpoint-based, characterizations of the well-founded semantics for logic programs in the general setting of bilattices. This work lights the role of the Closed World Assumption, used in the well-founded semantics as a carrier of falsehood, and shows that the definition of that semantics does not require any separation of positive and negative information nor any program transformation.
Abstract: A graph G is A-l-choosable for an Abelian group A and an integer l<=|A| if for each orientation of G, each edge-labeling phi:E->A and each list-assignment L:V->{A\choose l} there exists a vertex coloring c:V->A with c(v)\in L(v) for each vertex v and with c(v)-c(u)<>phi(uv) for each oriented edge uv of G. We prove a dichotomy result on the computational complexity of the problem. In particular, we show that the problem is Pi_2^P-complete if l>=3 for any group A and it is polynomial-time solvable if l=1,2.
Abstract: In learning theory and genetic programming, OBDDs are used to represent approximations of Boolean functions. This motivates the investigation of the OBDD complexity of approximating Boolean functions with respect to given distributions on the inputs. We present a new type of reduction for one--round communication problems that is suitable for approximations. Using this new type of reduction, we prove the following results on OBDD approximations of Boolean functions: 1) We show that OBDDs approximating the well--known hidden weighted bit function for uniformly distributed inputs with constant error have size $2^{\Theta(n^{1/4})}$, improving a previously known result. 2) We prove that for every variable order $\pi$ the approximation of some output bits of integer multiplication with constant error requires $\pi$-OBDDs of exponential size.
Abstract: The information contained in a string $x$ about a string $y$ is defined as the difference between the Kolmogorov complexity of $y$ and the conditional Kolmogorov complexity of $y$ given $x$, i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small additive term $O(\log \C(x,y))$. We investigate if symmetry of information can hold in the polynomial time bounded setting. In particular, we investigate symmetry of information for some variants of distinguishing complexity $\CD$, where $\CD(x)$ is the length of a shortest program which accepts $x$ and only $x$. We show relativized worlds where symmetry of information fails in a strong way for deterministic and nondeterministic polynomial time distinguishing complexities $\CD^{\poly}$ and $\CND^{\poly}$. On the other hand, fornondeterministic polynomial time distinguishing with randomness, $\CAM^{\poly}$, we prove that symmetry of information holds for most pairs of strings in any set in $\NP$. In proving this last statement we extend a recent result of Buhrman et al.[BLvM04], which may be of independent utility.
Abstract: We consider the decidability of existence of solutions to language equations involving the operations of shuffle and deletion along trajectories. These operations generalize the operations of catenation, insertion, shuffle, quotient, sequential and scattered deletion, as well as many others. Our results are constructive in the sense that if a solution exists, it can be effectively represented. We show both positive and negative decidability results.
Abstract: The protein folding problem, i.e., the computational prediction of the three-dimensional structure of a protein from its amino acid sequence, is one of the most important and challenging problems in computational biology. Since a complete simulation of the folding process of a protein is far too complex to handle, one tries to find an approximate solution by using a simplified, abstract model. One of the most popular models is the so-called HP model, where the hydrophobic interactions between the amino acids are considered to be the main force in the folding process, and the folding space is modelled by a two- or three-dimensional grid lattice. In this paper, we will present some approximation algorithms for the protein folding problem in the HP model on an extended grid lattice with plane diagonals. The choice of this lattice removes one of the major drawbacks of the original HP model, namely the bipartiteness of the grid which severely restricts the set of possible foldings. Our algorithms achieve an approximation ratio of 1.733 for the two-dimensional and of 1.6 for the three-dimensional lattice. This improves significantly over the best previously known approximation ratios for the protein folding problem in the HP model on any lattice.
Abstract: Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to the Brzozowski's dot-depth hierarchy and some its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach).
Abstract: Optimization problems considered in the literature generally assume a passive environment that does not react to the actions of an agent. In this paper, we introduce and study a class of optimization problems in which the environment plays an active, adversarial role and responds dynamically to the actions of an agent; this class of problems is based on the framework of quantified constraint satisfaction. We formalize a new notion of approximation algorithm for these optimization problems, and consider certain restricted versions of the general problem obtained by restricting the types of constraints that may appear. Our main result is a dichotomy theorem classifying exactly those restricted versions having a constant factor approximation algorithm.
Abstract: In this paper we present new techniques for Boolean Circuit Composition of NIPZK and PZK and significantly enlarge the class of known languages having such proofs. Our main result is taht all NC1 circuits compositions over a certain class of languages have NIZKPK. We also extend the class of known lagugaes in PZK by allowing composition over self-reducible languages with respect to polynomial-time monotone circuits with fan-out > 1 and certain additional restrictions on the allowed gates.
Abstract: We study the computational complexity of the isomorphism and equivalence problems on systems of equations over a fixed finite group. We show that the equivalence problem is in P if the group is Abelian, and coNP-complete if the group is non-Abelian. We prove that if the group is non-Abelian, then the problem of deciding whether two systems of equations over the group are isomorphic is coNP-hard. If the group is Abelian, then the isomorphism problem is graph isomorphism hard. Moreover, if we impose the restriction that all equations are of bounded length, then we prove that the isomorphism problem for systems of equations over finite Abelian groups is graph isomorphism complete. Finally we prove that the problem of counting the number of isomorphisms of systems of equations is no harder than deciding whether there exist any isomorphisms at all.
Abstract: We define new subclasses of the class of irreducible sofic shifts.These classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by B. Marcus. We give effective characterizations of these classes with the syntactic semigroups of the shifts.
Abstract: We formulate and prove here an Eilenberg- and Reiterman-type theorems for pseudovarieties of idempotent semiring homomorphisms. We also initiate the study of quite significant classes of languages - the so-called multiliteral varieties of regular languages.
Abstract: In this paper we introduce number-decreasing cellular automata which are a super-class of standard number-conserving cellular automata. It is well-known that the property of being number-conserving is decidable in quasi-linear time. In this paper we prove that the similar property of being number-decreasing is dimension sensitive \ie it is decidable is for one-dimensional cellular automata and undecidable for automata of dimension 2 or greater. This is the only known example of dimension sensitive property unrelated to other dimension sensitive properties like surjectivity and injectivity.
Abstract: We study the problem of optimal preemptive scheduling with respect to a general target function. Given n jobs with associated weights and m \leq n uniformly related machines, one aims at scheduling the jobs to the machines, allowing preemptions but forbidding parallelization, so that a given target function of the loads on each machine is minimized. This problem was studied in the past in the case of the makespan. Gonzalez and Sahni (1978) and later Shachnai, Tamir and Woeginger (2002) devised a polynomial algorithm that outputs an optimal schedule for which the number of preemptions is at most 2(m-1). We extend their ideas for general symmetric, convex and monotone target functions. This general approach enables us to distill the underlying principles on which the optimal makespan algorithm is based. More specifically, the general approach enables us to identify between the optimal scheduling problem and a corresponding problem of mathematical programming. This, in turn, allows us to devise a single algorithm that is suitable for a wide array of target functions, where the only difference between one target function and another is manifested through the corresponding mathematical programming problem.
Abstract: In this paper we afford the problem of model checking for well structured Communicating Hierarchical Machines (CHMs), i.e. Finite State Machines with additional features of hierarchy and concurrency. For model checking we follow the automaton theoretic approach, defining an algorithm which solves the problem of model checking without flattening the structure of CHMs.
Abstract: In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce the notion of efficient fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is efficiently fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts to characterize optimization problems with polynomial time approximation schemes.
Abstract: Although it is decidable whether or not a word equation is satisfiable, due to Makanin's results, the structure of all solutions in general is difficult to describe. In particular, it was proved by Hmelevskii that the solutions of xyz=zvx cannot be finitely parametrized, contrary to the case of equations in three unknowns. In this paper we give a short, elementary proof of Hmelevkii's result. We also give a simple, necessary, non-sufficient condition for an equation to be non-parametrizable.
Abstract: This paper proves lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordered search problem. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our proof employs an argument that (i) commences with the faulty assumption that a quantum algorithm of low query complexity exists, (ii) select any incompressible input, and (iii) constructs another algorithm that compresses the input, which leads to a contradiction. Using this ``algorithmic'' argument, we show that the multiple-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation supplemented by advice. This main theorem and its proof technique can be applied to two important notions in structural complexity theory: nonadaptive (truth-table) reducibility and autoreducibility.
Abstract: Let $G$ be a simple digraph. The {\em dicycle packing number} of $G$, denoted $\nu_c(G)$, is the maximum size of a set of arc-disjoint directed cycles in $G$. Let $G$ be a digraph with a nonnegative arc-weight function $w$. A function $\psi$ from the set ${\cal C}$ of directed cycles in $G$ to $R_+$ is a {\em fractional dicycle packing} of $G$ if $\sum_{e \in C \in {\cal C}} {\psi(C)} \leq w(e)$ for each $e \in E(G)$. The {\em fractional dicycle packing number}, denoted $\nu_c^*(G,w)$, is the maximum value of $\sum_{C \in {\cal C}} \psi(C)$ taken over all fractional dicycle packings $\psi$. In case $w \equiv 1$ we denote the latter parameter by $\nu_c^*(G)$. Our main result is that $\nu_c^*(G) - \nu_c(G)=o(n^2)$ where $n=|V(G)|$. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least $\nu_c(G)-o(n^2)$ in randomized polynomial time. Since computing $\nu_c(G)$ is an NP-Hard problem, and since almost all digraphs have $\nu_c(G)=\Theta(n^2)$ our result is a FPTAS for computing $\nu_c(G)$ for almost all digraphs.
Abstract: We investigate the complexity of membership problems for {union,intersection,complement,+,x}-circuits computing sets of integers. These problems are a natural modification of the membership problems for circuits computing sets of natural numbers studied by McKenzie and Wagner (2003). We show that there are several membership problems for which the complexity in the case of integers differs significantly from the case of the natural numbers: Testing membership in the subset of integers produced at the output of a {union,+,x}-circuit is NEXPTIME-complete, whereas it is PSPACE-complete for the natural numbers. As another result, evaluating {complement,+}-circuits is shown P-complete for the integers and PSPACE-complete for the natural numbers. The latter result extends work by McKenzie and Wagner (2003) in nontrivial ways. Furthermore, the case {x} is shown $\tn{NL}\land\oplus\tn{L}$-complete, and several other cases are resolved.
Abstract: We show that one cannot rule out even a single possibility for the value of an arithmetic circuit on a given input using an NC algorithm, unless P collapses to NC (i.e., unless all problems with polynomial-time sequential solutions can be efficiently parallelized). Thus excluding any possible solution in this case is as hard as finding the solution exactly. The result is robust with respect to NC algorithms that err (i.e., exclude the correct value) with small probability. We also show that P collapses all the way down to $\NC^1$ when the characteristic of the field that the problem is over is sufficiently large (but in this case under a stronger elimination hypothesis that depends on the characteristic).
Abstract: Bidimensionality is a powerful tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper completes the theory of bidimensionality for graphs of bounded genus (which is a minor-excluding family). Specifically we show that, for any problem whose solution value does not increase under contractions and whose solution value is large on a grid graph augmented by a bounded number of handles, the treewidth of any bounded-genus graph is at most a constant factor larger than the square root of the problem's solution value on that graph. Such bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, r-dominating set, connected dominating set, planar set cover, and diameter. This result has many algorithmic and combinatorial consequences. On the algorithmic side, by showing that an augmented grid is the prototype bounded-genus graph, we generalize and simplify many existing algorithms for such problems in graph classes excluding a minor. On the combinatorial side, our result is a step towards a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour.
Abstract: We explore the possibility of reconfiguring, or ``morphing'', one simple polygon to another, maintaining simplicity, and preserving some properties of angles and edge lengths. In linkage reconfiguration, edge lengths must be preserved. By contrast, a {\em monotone morph} preserves edge directions and changes edge lengths monotonically. A monotone morph is possible only for {\em parallel} polygons with corresponding edges parallel. Our main results are that monotone morphs exist for parallel pairs of polygons that are: (1) convex; or (2) orthogonally convex. Our morphs either move vertices in straight lines, or change few edge lengths at once. On the negative side, we show that it is NP-hard to decide if two simple parallel orthogonal polygons have a monotone morph. We establish which of these resultsextend to 3-dimensional polyhedra.
Abstract: Brandenburg and (implicitly) Dejean introduced the concept of repetition threshold: the smallest real number $\alpha$ such that there exists an infinite word over a $k$-letter alphabet that avoids $\beta$-powers for all $\beta > \alpha$. We generalize this concept to include the lengths of the avoided words. We give some conjectures supported by numerical evidence and prove three of these conjectures. As a consequence of one of our results, we show that the pattern $ABCBABC$ is $2$-avoidable. This resolves a question left open in Cassaigne's thesis.
Abstract: The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.
Abstract: A binary language-theoretic operation is proposed, which is dual to the concatenation of languages in the same sense as the universal quantifier in logic is dual to the existential quantifier; the dual of Kleene star is defined accordingly. These operations arise whenever concatenation or star appears in the scope of negation. The basic properties of the new operations are determined in the paper. Their use in regular expressions and in language equations is considered, and it is shown that they often eliminate the need of using negation, at the same time having an important technical advantage of being monotone. A generalization of context-free grammars featuring dual concatenation is introduced and proved to be equivalent to the recently studied Boolean grammars.
Abstract: We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs. We show that the problems are rather closely related for all amounts $c$ of deletion: (1) For all $c \geq 1$, $\gi \equiv^{l}_{iso} \vdc_{c}$, $\gi \equiv^{l}_{iso} \edc_{c}$, $\gi \leq^{l}_{m} \lvd_c$, and $\gi \equiv^{p}_{iso} \led_c$. (2) For all $c \geq 1$ and $k \geq 2$, $\gi \equiv^{p}_{iso} \kvsdc_c$ and $\gi \equiv^{p}_{iso} \kesdc_c$. (3) For all $c \geq 1$ and $k \geq 2$, $\gi \leq^{l}_{m} \klvsd_c$. In particular, for all $c \geq 1$, $\gi \equiv^{p}_{iso} \tolvsd_c$. (d) For all $c \geq 1$ and $k \geq 2$, $\gi \equiv^{p}_{iso} \klesd_c$. For many of these, even the $c = 1$ cases were not known. Similar to the definition of reconstruction numbers $vrn_{\exists}(G)$~\cite{har:j:recon-num} and $ern_{\exists}(G)$ (see p. 120 of~\cite{lauri-scap:b:autorec}), we introduce two new graph parameters, $vrn_{\forall}(G)$ and $ern_{\forall}(G)$, and give an example of a family $\{G_n\}_{n \geq 4}$ of graphs on $n$ vertices for which $vrn_{\exists}(G_n) < vrn_{\forall}(G_n)$. For every $k \geq 2$ and $n \geq 1$, we give an example of a collection of $k$ graphs on $O(2^{k}n)$ vertices with $\Omega(2^{n})$ 1-vertex-preimages, i.e., for each $k$, one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.
Abstract: This paper revisits design and analysis techniques for fixed parameter algorithms for {\sc Planar Dominating Set} and other problems on planar structures. As our main result, we use new geometric arguments concerning treewidth-based algorithms to show that determining whether a planar graph $G$ has a dominating set of size $k$ can be solved in $O(2^{ 16.4715\sqrt{k}} n)$ steps. This result improves on the best known treewidth-based algorithm by Kanj and Perkovi\v c that runs in time $O(2^{27\sqrt{k}}n)$. Our main result nearly matches the new branchwidth-based algorithm for {\sc Planar Dominating Set} by Fomin and Thilikos that runs in time $O(2^{15.13 \sqrt{k}}k +n^3)$. Algorithms for other problems on planar structures are explored. In particular, we show that {\sc Planar Red/Blue Dominating Set} can besolved in time $O(2^{24.551 \sqrt{k}}n)$. This leads to the main results, namely, that faster parameterized algorithms can be obtained for a variety of problems that can be described by planar boolean formulae. This gives the beast-known parameterized algorithms for {\sc Planar Vertex Cover}, {\sc Planar Edge Dominating Set}, and {\sc Face Cover}.
Abstract: Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^a}) that have trivial dimension and measure in ESPACE. This paper gives an exact characterization of effective scaled dimension in terms of resource-bounded Kolmogorov complexity. We can know view each result on the scaled dimension of a class of languages as upper and lower bounds on the Kolmogorov complexity of the languages in the class. We prove a Small Span Theorem for Turing reductions that implies the class of P/poly-Turing-hard sets for ESPACE has (-3)rd-pspace dimension 0. As a consequence we have a nontrivial upper bound on the Kolmogorov complexity of all hard sets for ESPACE for this very general nonuniform reduction, P/poly-Turing. This is, to our knowledge, the first such bound. We also show that this upper bound does not hold for most decidable languages, so P/poly-Turing-hard languages are unusually simple.
Abstract: We study the complexity of the inclusion, equivalence, and intersection problem for simple regular expressions arising in practical XML schemas. These basically consist of the concatenation of factors where each factor is a disjunction of strings possibly extended with `$*$' or `$?$'. We obtain lower and upper bounds for various fragments of simple regular expressions. Although we show that inclusion and intersection are already intractable for very weak expressions, we also identify some tractable cases. For equivalence, we only prove an initial tractability result leaving the complexity of more general cases open. The main motivation for this research comes from database theory, or more specifically XML and semi-structured data. We namely show that all lower and upper bounds for inclusion and equivalence, carry over to the corresponding decision problems for extended context-free grammars and single-type tree grammars, which are abstractions of DTDs and XML Schemas, respectively. For intersection, we show that the complexity only carries over for DTDs.
Abstract: In this work, we consider an interesting variant of the well-studied KP model for selfish routing that reflects some influence from the much older Wardrop. In the new model, user traffics are unsplittable, while social cost is the expectation of the sum, over all links, of a certain polynomial evaluated at the total latency incurred by all users choosing the link; we call it polynomial social cost. We are interested in evaluating Nash equilibria in this model, and we use the Price of Anarchy as our evaluation measure.
Abstract: We consider infinite antagonistic games over finite graphs. We present conditions that, whenever satisfied by the payoff mapping, assure for both players positional (memoryless) optimal strategies. We show that all popular payoff mappings, such as mean payoff, discounted, parity as well as several other payoffs satisfy these conditions. This approach allows to give a uniform treatment of otherwise disparate results concerning the existence of positional optimal strategies.
Abstract: A proper coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. The related notion is r-bounded coloring where each of the color classes is of cardinality at most r. We consider the problems to determine for a given graph G (and a given integer r) whether G has an equitable (r-bounded) coloring. We prove that both problems can be solved in polynomial time on graphs of bounded treewidth.
Abstract: We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph. We identify a new ``controlled'' version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. Under reasonable assumptions the problem belongs to the complexity class \textsc{NP}$\cap$\textsc{coNP}. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player Max selects a strategy (one edge in each controlled vertex) and player Min responds byevaluating shortest paths to the sink in the remaining graph. Then Max locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity \[\min(poly\cdot W,\;2^{O(\sqrt{n\log n})}),\] which is simultaneously pseudopolynomial ($W$ is the maximal absolute edge weight) and subexponential in the number of vertices $n$. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).
Abstract: A partial information algorithm for A computes on input words x_1,...,x_m a set of bitstrings containing \chi_A(x_1,...,x_m). For a family D of sets of bitstrings of length m, A is in P[D] if there is a polynomial time partial information algorithm that always outputs a set from D. This definition covers notions like p-selective, approximable, cheatable, strongly membership comparable, and easily countable languages. For the case m=2 we investigate whether for families D_1 and D_2 the languages in P[D_1] are reducible to languages in P^X[D_2] for some X in PH or in EXP. Beigel, Fortnow and Pavan , and Till Tantau already achieved some results in this respect. We achieve results for all remaining non-trivial pairs of classes P[D] for m=2. We show: 1. 2-cheatable languages are 1-tt \Delta^p_2-reducible to languages in \Delta^p_2[MIN_2}. 2. Languages in P[SEL_2 \cup { xor_2 } ] are 1-tt \Delta^p_2-reducible to some \Delta^p_2-selective languages. 3. 2-countable languages are 1-tt \Delta^p_3-reducible to \Delta^p_3 strongly 2-membership comparable languages. 4. 2-membership comparable languages are 1-tt EXP-reducible to EXP strongly 2-membership comparable languages. 5. There are easily 2-countable languages not Turing reducible to languages in EXP[BOTTOM_2]. 6. There are languages in P[BOTTOM_2] not 1-tt EXP-reducible to EXP-selective languages.
Abstract: Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f. For several subclasses of operations we prove tight upper and lower bounds for the generation problems. For example, we prove exponential-time upper and lower bounds for generation problems of length-monotonic polynomial-time computable operations. Other bounds involve classes like NP and PSPACE. Here the class of bivariate polynomials with positive coefficients turns out to be the most interesting class of operations. We show that many of the corresponding generation problems belong to NP. However, we do not know this for all of them, e.g., for x^2+2y this is an open question. We prove NP-completeness for polynomials x^a*y^b*c where a,b,c>0. Also, we show NP-hardness for polynomials like x^2+2y. As a by-product we obtain NP-completeness of an extended sum-of-subset problem SOS(c), c>0, where the usual sum is not taken throughout the selected wheights, but over the selected weights, taken to the c-th power.
Abstract: We introduce a natural class of cellular automata characterised by a property of the local transition law without any assumption on the states set. We investigate some algebraic properties of the class and show that it contains intrinsically universal cellular automata. In addition we show that Rice's theorem for limit sets is no longer true for that class, although infinitely many properties of limit sets are still undecidable.
Abstract: We consider semistructured data as rooted edge-labeled directed graphs, and path inclusion constraints on these graphs. In this paper, we show that we can extract from a datum D a finite set C_f of word inclusions, which implies exactly every word inclusion satisfied by D. Then, we give a new decision algorithm for the implication problem of a constraint (p < q) by a set of constraints (p_i < u_i) where p, q, and the p_i's are regular path expressions and the u_i's are non empty paths, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and Alechina et al. Moreover, in the case of a set of word equalities (u_i = v_i), we give a more efficient decision algorithm for the implication of a word equality (u = v), improving the more general algorithm of P. Buneman et al., and we prove that, in this case, the implication problem for non deterministic models or for (complete) deterministic models are equivalent.
Abstract: The purpose of this article is to describe a way to simulate any 3-dimensional cellular automaton with a 2-dimensional cellular automaton. We will present the problems that arise when changing the dimension, propose solutions and discuss the main properties of the obtained simulation.
Abstract: We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds. An important example is this: Razborov and Wigderson showed that a certain function f in ACC0 cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and a layer of AND gates at the bottom. We observe that a simple combination of their result with the Hastad switching lemma yields the following seemingly much stronger result: The same function f cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and an arbitrary AC0 circuit feeding the MAJORITY gates.
Abstract: The paper deals with updates of XML documents that satisfy a given schema, e.g, a DTD. In this context, when a given update violates the schema, it might be the case that this update is accepted, thus implying to change the schema. Our method is intended to be used by a data administrator who is an expert in the domain of application of the database, but who is not required to be a computer science expert. Our approach consists in proposing different schema options that are derived from the original one. The method is consistency-preserving: documents valid with respect to the original schema remain valid. The schema evolution is implemented by an algorithm (called GREC) that performs changes on the graph of a finite state automaton and that generates regular expressions for the modified graphs. Each regular expression proposed by GREC is a choice of schema given to the administrator.
Abstract: In this paper we study the membership and vector reachability problems for labelled transition systems with row-monomial transformations. We show the decidability of these problems for row-monomial martix semigroups over rationals and extend these results to the wider class of matrix semigroups. After that we apply our methods to reachability problems for a class of transition systems which turn out to be equivalent to specific counter machines.
Abstract: A finite automaton, simply referred to as a {\em robot}, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any $K$-state robot and any $d\geq 3$, there exists a planar graph of maximum degree $d$ with at most $K+1$ nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter $D$ and maximum degree $d$, a robot needs $\Omega(D\log{d})$ memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth$D+1$ enables a robot to explore any graph of diameter $D$ and maximum degree $d$ using a memory of size $O(D\log{d})$ bits. We thus prove that the worst case space complexity of graph exploration is $\Theta(D\log{d})$ bits.
Abstract: We consider parallel knock-out schemes, a procedure on graphs introduced by Lampert and Slater in 1997 in which each vertex eliminates exactly one of its neighbors in each round. We are considering cases in which after a finite number of rounds, where the minimimum number is called the parallel knock-out number, no vertices of the graph are left. We derive a number of combinatorial and algorithmical results on parallel knock-out numbers; in particular we discuss sparse graphs, trees, and claw-free graphs.
Abstract: The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed among the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning rectangular queries of higher-dimensional data. For this problem, we give a declustering scheme with an additive error of $O_d(\log^{d-1} M)$ independent of the data size, where $d$ is the dimension, $M$ the number of storage devices and $d-1$ not larger than the smallest prime power in the canonical decomposition of $M$. Thus, in particular, our schemes work for arbitrary $M$ in two and three dimensions, and arbitrary $M \ge d-1$ that is a power of two. These cases seem to be the most relevant in applications. For a lower bound, we show that a recent proof of a $\Omega_d(\log^{\frac{d-1}{2}} M)$ bound contains a critical error. Using an alternative approach, we establish this bound.
Abstract: The Minimum 2SAT-Deletion problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems \cite{KST}, and its approximability is largely open. We prove a lower approximation bound of $8\sqrt 5-15\approx 2.88854$, improving the previous bound of $10\sqrt5-21\approx 1.36067$ by Dinur and Safra \cite{DS}. For highly restricted instances with exactly 4 occurences of every variable we provide a lower bound of $\frac32$. Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated). We further prove that any $k$-approximation algorithm for Minimum 2SAT-Deletion polynomially reduces to a $(2-\frac{2}{k+1})$-approximation algorithm for the Minimum Vertex Cover problem. One ingredient of these improvements is our proof that for the Minimum Vertex Cover problem restricted to graphs with a perfect matching its threshold on polynomial time approximability is the same as for the general Minimum Vertex Cover problem. This improves also on results of Chen and Kanj \cite{CHK2}.
Abstract: Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting requires in a random graph of certain density $O (\ln n)$ steps, where $n$ denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in $O(D)$ steps, where $D$ denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting, graphs exist in which spreading an information requires $\Omega (n^2)$ steps. On the other hand, some graphs which require $\Omega (n \ln n)$ steps to spread the information in the traditional broadcast model, allow very fast agent based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability $1-o(1/n)$.
Abstract: For the earliest arrival flow problem one is given a network $G=(V, A)$ with capacities $u(a)$ and transit times $\tau(a)$ on its arcs $a \in A$, together with a source and a sink vertex $s, t \in V$. The objective is to send flow from $s$ to $t$ that moves through the network over time, such that for each point in time $\theta \in [0,T)$ the maximum possible amount of flow reaches $t$. If, for each $\theta \in [0,T)$ this flow is a maximum flow for time horizon $\theta$, then it is called \emph{earliest arrival flow}. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time $\theta$ depends on the flow on this particular arc at that time $\theta$. For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define an optimization version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each $\theta \in [0,T)$, need only $\alpha$-times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on $\alpha$; furthermore, we present a constant factor approximation algorithm for this problem. Finally, we give some computational results to show the practicability of the designed approximation algorithm.
Abstract: An infinite binary sequence is disjunctive if every binary word occurs as a subword in the sequence. For a computational analysis of disjunctive sequences we can identify an infinite 0-1-sequence either with its prefix set or with its corresponding set, where a set $A$ of binary words corresponds to a sequence $\alpha$ if $\alpha$ is the characteristic sequence of $A$. Most of the previous investigations of disjunctive sequences have dealt with prefix sets. Here, following the more common point of view in computability theory, we focus our investigations on the sets corresponding to disjunctive sequences. We analyze the computational complexity and the Chomsky complexity of sets corresponding to disjunctive sequences. In particular, we show that no such set is regular but that there are linear languages with disjunctive characteristic sequences. Moreover, we discuss decidability questions. Here our main results are that the disjunctivity problem for Chomsky-0-grammars is $\Pi^0_3$-complete while the corresponding problem for linear or context free or context sensitive languages is $\Pi^0_2$-complete. The latter implies that, for any language class $\FU{C}$ which contains the linear languages, the class of the languages in $\FU{C}$ corresponding to disjunctive sequences is not recursively presentable.
Abstract: The silhouette of a polyhedron is an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex polyhedra such that the silhouette satisfies certain properties. Specifically, we give algorithms to find all projections of a convex polyhedron such that a given set of edges, faces and/or vertices appear in the silhouette. We present an algorithm to solve this problem in O(k^2) time for k edges. For orthogonal projections, we give an improved algorithm that is fully adaptive in the number c of connected components formed by the edges, and has a time complexity of O(k\log k + kc). We then generalize this algorithm to edges and/or faces appearing in the silhouette.
Abstract: This paper deals with the compositional verification of sequential programs. This consists in deciding whether or not a given set of local structural properties of the functions of a program implies a given global behavioural property of the program. Here we consider properties expressed in monadic second-order logic dealing with the control flow of the program and the function calls occuring during its execution. This problem has been investigated in relation with the security of open multi-application smart cards. We prove that the compositionality is a decidable problem for sequential programs whose control-flow graphs are of tree-width less than a fixed integer value, which includes in particular structured programs.
Abstract: Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and \textit{vice-versa}. In this way complete problems for the classes $\prom\BPP$ (promise $\BPP$) and $\prom\BQP$ (promise $\BQP$) are given when changing the semiring from $(\Rat^+,{}+{},{}\cdot{})$ to the field $(\Rat,{}+{},{}\cdot{})$. Moreover, by variants of the problem under consideration, classes like $\PP$,\ $\NP$,\ $\textnormal{C}_{=}\P$, its complement $\co \textnormal{C}_{=}\P$, thepromise version of Valiant's class $\UP$, its generalization promise $\SPP$, and unique polytime $\US$ are captured as problem property and the semiring varies.
Abstract: So far the least growth rate known for a divergent inherent ambiguity function was logarithmic. This paper shows that for each computable divergent total non-decreasing function $f:\N \to \N$ there is a context-free language $L$ with a divergent inherent ambiguity function $g$ below $f$. This proves that extremely slow growing divergent inherent ambiguity functions exist. For instance there is a context-free language $L$ with infinite inherent ambiguity below $\log^*$.
Abstract: We devise an efficient protocol by which a series of two-person games G_i with unique winning strategies can be combined into a single game G with a unique winning strategy, even when the result of G is a non-monotone function of the results of the G_i that is unknown to the players. In computational-complexity terms, we show that the class UAP of Niedermeier and Rossmanith [NiRo98] of languages accepted by unambiguous polynomial-time alternating TMs is self-low, i.e. UAP^UAP = UAP. It follows that UAP contains the Graph Isomorphism problem, nominally improving the problem's classification into SPP by Arvind and Kurur [ArKu02], since UAP was shown a subclass of SPP by [NiRo98]. We give some other applications, oracle separations, and results on problems related to unique-alternation formulas.
Abstract: How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. As part of our work we develop a new proof technique, which builds diagonalizations against certificates directly into a circuit.
Abstract: We propose a generalisation of Winskel's event structures, matching the expressive power of arbitrary Petri nets. In particular, our event structures capture resolvable conflict, besides disjunctive and conjunctive causality. With every event structure we associate a family of configurations, a propositional theory and a Petri net. We characterise a variety of classes of event structures in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets.
Abstract: We study the on-line versions of two fundamental graph problems, maximum independent set and minimum coloring, for the case of {\em disk graphs} which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds; we also present an improved upper bound for on-line coloring.
Abstract: Let $G=(V,E)$ be a (directed) graph with vertex set $V$ and edge (arc) set $E$. Given a set $\cP$ of source-sink pairs of vertices of $G$, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all or at least one of the given source-sink pairs of $\cP$. For undirected graphs, we show that the enumeration problem for conjunctions of paths can be solved in incremental polynomial time. For directed graphs, while we show that the enumeration problems for both general path-conjunction and extensions of path disjunction are NP-hard, even for a disjoint set of source-sink pairs, we give a polynomial delay algorithm for enumerating minimal sets of arcs connecting two given nodes $s_1$ and $s_2$ to each vertex of two given subsets of vertices $T_1$ and $T_2$, respectively.