STACS 95

Infinite two-person games are a natural framework for the study of reactive nonterminating programs. The effective construction of winning strategies in such games is an approach to the synthesis of reactive programs. We describe the automata theoretic setting of infinite games (given by “game graphs”), outline a new construction of winning strategies in finite-state games, and formulate some questions which arise for games over effectively presented infinite graphs.

Assume that n players are represented by n reals, uniformly distributed over the unit interval.We assume that the error probability of a comparison game between two players depends linearly on the distance between the players. Using sequential analysis approach, we present an algorithm to estimate the maximum ξ of the players with an error less than ε.Mean cost, variance and centered moments generating function are analyzed.

This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform many-one reductions that are computed by polynomial-size circuits (P/Poly-many-one reductions). Every weakly P/Poly-many-one-complete problem is shown to have a dense, exponential, nonuniform complexity core. An exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/Poly-Turing-complete problems is established. More importantly, the P/Poly-many-one-complete problems are shown to be unusually simple elements of ESPACE, in the sense that they obey nontrivial upper bounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE. More generally, a Small Span Theorem for P/Poly-many-one reducibility in ESPACE is proven and used to show that every P/Poly-many-one degree -including the complete degree — has measure 0 in ESPACE. (In contrast, almost every element of ESPACE is weakly P-many-one complete.) All upper and lower bounds are shown to be tight.

We study a variation on classical key-agreement and consensus problems in which the key space S is the range of a random variable that can be sampled. We give tight upper and lower bounds of [log₂k] bits on the communication complexity of agreement on some key in S, using a form of Sperner's Lemma, and give bounds on other problems. In the case where keys are generated by a probabilistic polynomial-time Turing machine, we show agreement possible with zero communication if every fully polynomial-time approximation scheme (fpras) has a certain symmetry-breaking property.

Allender [All89] showed that if there are dense P languages containing only a finite set of Kolmogorov-simple strings, then all pseudorandom generators are insecure. We extend this by proving that if there are dense P (or even BPP) languages containing only a sparse set of Kolmogorovsimple strings, then all pseudorandom generators are insecure.

Classes of bounded counting type are a generalization of complexity classes with finite acceptance types. The latter ones are defined via nondeterministic machines whose number of accepting paths up to a certain maximum is responsible for the question of acceptance of the input. For the classes of bounded counting type each computation path may have one of k possible results from the set {0,⋯, k-1} (k≥2), and we count the number of paths having result 1, as well as the number of paths having result 2, etc. Each result (except 0) is counted up to a certain maximum, and the vector formed by these numbers is responsible for the acceptance question.In this paper we design and prove correctness of an algorithm deciding the question “Is there an oracle separating C₁ from C₂?” for arbitrary classes C₁ and C₂ of bounded counting type. For the special case of classes of finite acceptance types we can give a direct solution to the separability question, thus solving an open problem from [H94a].Moreover, we note that a surprising consequence on relativizable closure properties of #P can be obtained from these investigations [H94c].

We say an integer polynomial p, on Boolean inputs, weakly m-represents a Boolean function f if p is non-constant and is zero (mod m) whenever f is zero. In this paper we prove that if a polynomial weakly m-represents the Mod_q function on n inputs, where q and m are relatively prime and m is otherwise arbitrary, then the degree of the polynomial is Ω(n). This generalizes previous results of Barrington, Beigel and Rudich [BBR] and Tsai [Tsai], which held only for constant (or slowly growing) m. The proof technique given here is quite different and somewhat simpler. We use a method in which the inputs are represented as complex qth roots of unity (following Barrington and Straubing [BS]). The representation is used to take advantage of a variant of the inverse Fourier transform and elementary properties of the algebraic integers. As a corollary of the main theorem and the proof of Toda's theorem, if q, p are distinct primes, any depth-three circuit which computes the Mod_q function, and consists of an equals gate at the output, Mod_p-gates at the next level, and AND-gates of small fan-in at the inputs, must be of exponential size. In terms of Turing machine complexity classes, there is an oracle A such that $$Mod_q P^A \nsubseteq C_ = P^{Mod_p P^A }$$ .

Using a lower bound argument based on probabilistic communication complexity it will be shown that iterated multiplication of n-bit numbers modulo polylog (n)-bit integers cannot be done efficiently by depth two threshold circuits. As a consequence we obtain that for iterated multiplication of n-bit numbers, in contrast to multiplication, powering, and division, decomposition via Chinese Remaindering does not yield efficient depth 3 threshold circuits.

In this paper, we prove the co-RNP-completeness (RNP=Random NP) of the following decision problem: “Given a 2-dimensional cellular automaton A, is A reversible when restricted to finite configurations extending a given row?” In order to prove this result, we introduce a polynomial reduction from problems concerning finite tilings into problems concerning cellular automata. Then we add to tile sets and cellular automata two probability functions and we prove that these problems are not only co-NP-complete, but co-RNP-complete too.

Two infinite words x and y are said to be subword equivalent if they have the same set of finite subwords (factors). The subword equivalence problem is the question whether two infinite words are subword equivalent. We show that, under mild hypotheses, the decidability of the subword equivalence problem implies the decidability of the ω-sequence equivalence problem, a problem which has been shown to be decidable by Čulik and Harju for morphic words (i.e. words generated by iterating a morphism).We prove that the subword equivalence problem is decidable for two morphic words, provided the morphisms are primitive and have bounded delays. We also prove that the subword equivalence problem is decidable for any pair of morphic words in the case of a binary alphabet. The subword equivalence problem is also shown to be decidable for two p-automatic words. We also prove a Cobham-like theorem: let p and q be two multiplicatively independent integers, and let x be a p-automatic word and let y be a q-automatic word, both with bounded gaps. If x and y are subword equivalent, then they are both ultimately periodic. Our results hold in fact for a stronger version, namely for the subword inclusion problem.

Let x be an infinite non periodic word on a finite alphabet A. For each position n, the separator of x at n is the smallest factor of x that starts at n and that does not appear before in x. Denote by Sx(n) the length of the separator of x at n and Sx the corresponding function. We consider the problem of computing Sx in the case where x is generated by iterating some morphism σ: A*→A*. We prove that if σ is q-uniform (q≥2) and x is circular then Sx is q-regular (in the sense of Allouche and Shallit [2], [23]), or, in other words that the corresponding formal power series that associates Sx(n) to the q-ary expression of n is rational (Salomaa, Soittola [22]).

The class of ω-languages recognized by systolic tree automata is introduced. That class extends the class of Büchi ω-languages and is closed under boolean operations. The emptiness problem for systolic tree automata on infinite sequences is decidable. A characterization of systolic tree ω-languages in terms of a (suitable) concatenation of (finitary) systolic tree languages is also provided.

In this paper we relate expressiveness of ω-automata to their complexity. Expressiveness is related to the different subclasses of the ω-regular languages that are accepted by automata that arise by restrictions on the acceptance conditions used. For example, different subclasses of the ω-regular languages arise from identifying the ω-languages with different classes and levels in the Borel hierarchy. Within the class of ω-regular languages, Wagner and Kaminski identified a strict hierarchy of languages induced by restricting the number of pairs allowed in a deterministic Rabin automaton (DRA).Complexity relates to the smallest size automaton required to realize an ω-regular language. Safra shows that there are ω-regular languages for which deterministic Streett automata (DSA) are exponentially smaller than nondeterministic Buchi automata; in contrast, we show that for every DSA or DRA whose language is in class G _δ , there exists a DBA of size linear in the original automaton. We show in particular that the language of a DRA is in class G _δ if and only if the language can be realized as a DBA on the same transition structure as the DRA. We present a simple construction to transform a DRA with h pairs and n states to an equivalent DRA with O(n.hk) states and k pairs (i.e. DR(n,h)→ DR(n.hk, k)), where k is the Rabin Index (RI) of the language-the minimum number of pairs required to realize the language as a DRA. We also present a construction to translate a DSA into a minimum-pair DRA, achieving a transformation DS(n,h)→DR(n.hk, r), where k is the Streett index (SI), and r the RI of the language.We prove that it is NP-hard to determine the RI (SI) of a language specified by a DRA (DSA). However, for a DRA (DSA) with h pairs, determining whether the RI (SI) is h, or any constant c, is in polynomial time.

Many of the linear transforms that are used in digital signalprocessing and other areas have a lot of symmetry properties. This makes the development of fast algorithms for them possible. The usual quadratic cost of multiplying with the matrix is reduced, in some cases to an almost linear complexity. Salient examples are the Fourier transform, the Cosine transform, linear maps with Toepliz matrices or convolutions. The article gives an exact definition of the notion of symmetry that leads to fast algorithms and presents a method to construct those algorithms automatically in the case of an existing symmetry with a soluble group. The results may serve to speed up the multiplication with a transform matrix and also to solve a linear system of equations with symmetry. Even though the construction is done at the level of abstract algebra, the derived algorithms for many linear transforms compare well with the best found in the literature [CoTu65, ElRa82, Ra68, RaYi90]. In most cases, where the new method was applicable, even the manually optimized algorithms [Nu81] were not better, while nothing more than the transform matrix and its symmetry were provided here to optain the results.

The classical problem of solving tridiagonal linear systems of equations is reconsidered. An extremely simple factorization of the system's matrix — implied by but not explicit in the known techniques — is identified and shown to belong to a class of transformations termed generalized scans. This class has an associative property which is the key to the complete parallelization of the technique. Due to the very weak constraints upon which it is based, the method extends naturally to arbitrary banded systems.

We present the first known (alphabet independent) algorithm for two-dimensional pattern matching which works in linear time and small space simultaneously. The searching phase of our algorithm works in O(1) space and is followed by pattern preprocessing performed in O(logm) space. Up to now there was not known even any efficient sublinear space algorithm for this problem. The main tools in our algorithm are several 2-dimensional variations of deterministic sampling, originally used in parallel pattern matching: small, frame and wide samples. Another novel idea used in our algorithm is the technique of zooming sequences: the sequences of nonperiodic decreasing parts of the pattern (samples) of similar regular shapes. Their regularity allows to encode the zooming sequences in small memory (logarithmic number of bits) while nonperiodicity allows to make shifts (kill positions as candidates for a match) in a way amortizing the work. The preprocessing phase is recursive, its structure is similar to the linear time algorithm for the selection problem. The stack of the recursion consists of logarithmic number of integers. Our algorithm is rather complicated, but all known alphabet-independent linear time algorithms (even with unrestricted space) for 2d-matching are quite complicated, too.

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. Our data structures can be updated after any such change in only polylogarithmic time, while a single-pair query is answered in sublinear time. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem.

We prove that — unless the polynomial hierarchy collapses at the second level — the size of a purely propositional representation of the circumscription CIRC(T) of a propositional formula T grows faster than any polynomial as the size of T increases. We then analyze the significance of this result in the related field of closed-world reasoning.

The paper presents a set-theoretic translation method for polymodal logics that reduces the derivability problem of a large class of propositional polymodal logics to the derivability problem of a very weak first-order set theory Ω. Unlike most existing translation methods, the one we propose applies to any normal complete finitely-axiomatizable polymodal logic, regardless if it is first-order complete. Moreover, the finite axiomatizability of Ω makes it possible to implement mechanical proof search procedures via the deduction theorem or more specialized and efficient techniques. In the last part of the paper, we briefly discuss the application of set T-resolution to support automated derivability in (a suitable extension of) Ω.

This paper presents algorithms for the automatic synthesis of real-time controllers by finding a winning strategy for certain games defined by the timed-automata of Alur and Dill. In such games, the outcome depends on the players' actions as well as on their timing. We believe that these results will pave the way for the application of program synthesis techniques to the construction of real-time embedded systems from their specifications.

We examine the meaning of causality in calculi for mobile processes like the π-calculus, and we investigate the relationship between interleaving and causal semantics for such calculi. We separate two forms of causal dependencies on actions of π-calculus processes, called subject and object dependencies: The former originate from the nesting of prefixes and are propagated through interactions among processes; the latter originate from the binding mechanisms on names. We develop a notion of causal bisimulation which distinguishes processes which differ for the subject or for the object dependencies. We show that this causal equivalence can be reconducted to, or implemented into, the ordinary interleaving observation equivalence. This allows us to exploit the simpler theory of the interleaving semantics to reason about the causal one.

The sizes of permutation networks for special sets of permutations are investigated. The study of the planar realization and the search for small but hard sets of permutations are also included. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here.The two main results are:(i)an asymptotically optimal permutation network of size 6·N·log log N for shifts of power 2.(ii)an asymptotically optimal planar permutation network of size Θ(N2·(loglog N/log N)2) for shifts of power 2.A consequence of our results is a construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one step in O(loglog N) communication steps. A new sorting network as well as an essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follow.

This paper presents and analyses efficient implementations of a so-called direct process on distributed memory machines (DMMs) that yieldsa simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n),a simulation of an n-processor PRAM on an n-processor arbitrary DMM with delay O(log log n/log log log n),an implementation of a static dictionary on an n-processor arbitrary DMM with parallel access time of O(log*n).We further prove a lower bound for executing the above process, showing that our implementations are optimal.

In this paper, the problem of routing messages along shortest paths in a distributed network without using complete routing tables is considered. In particular, the complexity of designing minimum (in terms of number of intervals) Interval Routing Schemes is analyzed under different requirements. For all the considered cases NP-hardness proofs are given, while some approximability results are provided. Moreover, relations among the different considered cases are studied.

In this paper, we introduce an on-line protocol which routes any set of packets along shortest paths through an arbitrary N-node network in O(congestion+diameter+log N) rounds, with high probability. This time bound is optimal up to the additive log N, and it was previously only reached for bounded-degree levelled networks.Further, we prove bounds on the congestion of random routing problems for Cayley networks and general node symmetric networks based on the construction of shortest paths systems. In particular, we give construction schemes for shortest paths systems and show that if every processor sends p packets to random destinations along the paths described in the paths system, then the congestion is bounded by O(p·diameter+log N), with high probability.Finally, we prove an (apparently suboptimal) congestion bound for random routing problems on randomly chosen regular networks.

If one folds in two parts a strip of paper several times on itself (all folds being parallel) one obtains after unfolding a sequence of “valley” and “ridge” folds. If one codes these folds over a two-letter alphabet, one obtains a paperfolding word associated to the sequence of folding instructions. A paperfolding sequence is an infinite paperfolding word.This paper is devoted to the effective construction of 2-uniform tag systems which generate every paperfolding sequences associated to ultimately periodic sequences of (un)folding instructions.

The growing context-sensitive languages (GCSL) are characterized by a nondeterministic machine model, the so-called shrinking two-pushdown automaton (sTPDA). Then the deterministic version of this automaton (sDTPDA) is shown to characterize the class of generalized Church-Rosser languages (GCRL). Finally, we prove that each growing context-sensitive language is accepted in polynomial time by some one-way auxiliary pushdown automaton with a logarithmic space bound (OW-auxPDA[log, poly]). As a consequence the class of (generalized) Church-Rosser languages and the class of context-free languages are incomparable under set inclusion, which verifies a conjecture of Mc-Naughton et al [MNO88].

A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable.We define the model of deterministic generalized automaton (DGA) and study the problem of its minimization. A DGA has the restriction that, for each state, the sets of words corresponding to the transitions of that state are prefix sets. We solve the problem of calculating the number of states of a minimal DGA for a given language, by giving a procedure that effectively constructs it starting from the minimal (conventional) deterministic automaton.

The problem of simulation of automata by neural networks is investigated. In the case of discrete networks with polynomially bounded weights, the optimal lower and upper bounds for the number of neurons necessary to simulate any finite automata of size n are presented. For the analog case we prove the 15-neuron upper bound for any finite automaton. By extending this construction we show that a 25-neuron network may simulate any Turing machine, and hence its behavior is undecidable.

My favorite example of a simple, “interesting” identity between regular expressions is $$(X^* .Y^* )^* = (X + Y)^*$$ This identity is true for ALL formal languages X, Y. An easy “folk” theorem shows that this can be verified by instantiating the language variables X, Y as single letters a,b and verifying that (a*.b*)*=(a+b)*. Checking this second, variable-free, identity is a routine matter of checking equivalence of finite automata. In the “algebraic” approach to concurrent process theory pioneered by Milner and Hoare, the original Kleene operators of language union, concatenation and star are enriched with various renaming and parallel combination operators. The simplest of these is the NONcommunicating parallel connective, ‖, corresponding to the shuffle or merge product of languages. Even this operator creates some interesting complications: the “interleaving identity” $$a\parallel b = a.b + b.a$$ is certainly true for single letters a,b, but the version with language variables $$X\parallel Y = X.Y + Y.X$$ is not true for all X,Y (let X=a, Y=bc).In this talk, I survey some of the results and open problems concerning language identities motivated by concurrent process theory. For example, Rabinovitch and I have shown that the validity problem for regular identities with shuffle is exponential space complete.

In this paper, we derive optimal lower and upper bounds on the multiparty communication complexity of boolean functions. We generalize the two-party method based on a crossing sequence argument introduced in [Y79] for the multiparty communication model. Lower bounds for the multiparty model have been a challenge since [DF89], where only the an upper bound on the number of bits exchanged by a deterministic algorithm computing a boolean function f(x₁,⋯, x _n ) was derived; namely of the order (k₀C₀)(k₁C₁)2, up to logarithmic factors, where k₁ and C₁ are the number of processors accessed and the bits exchanged in a nondeterministic algorithm for f, and k₀ and C₀ are the analogous parameters for the complementary function 1 — f.In our paper, we show that $$C_0 \leqslant n(1 + 2^{C_1 } )$$ and $$D \leqslant n(1 + 2^{C_1 } )$$ , where D is the number of bits exchanged by a deterministic algorithm computing f. We investigate also the power of a restricted multiparty communication model in which the coordinator is allowed to send at most one message to each party. We show that all the upper and lower bounds are optimal.

In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x₀,⋯, x_k−1 for which player i sees all inputs except x _i . The players have unlimited computational power. The objective is to minimize the amount of communication.We consider a restricted version of the multiparty communication game which we call the simultaneous messages model. The difference is that in this model, each of the k players simultaneously sends a message to a referee, who sees none of the input. The referee then announces the function value.We show demonstrate an exponential gap between the Simultaneous Messages and the Communication models for up to (log n)1−∈ players, for any ∈>0. The separation is obtained by comparing the respective complexities of the generalized addressing function, GAF_n,k, in each model. This work is motivated by an approach suggested by the results of Håstad & Goldmann (1991), Yao (1990), and Beigel & Tarui (1991) to separate ACC from complexity classes containing it.

We compare two notions of coding on traces, called coding and strong coding, in relation with the decision problem of the existence of a coding between two given trace monoids. We positively solve this problem if the first monoid is either a direct product of free monoids, or a free product of free commutative monoids. We show how the situation differs in the case of strong codings.

The paper solves the main open problem of [BFG94]. We show that given two dependence alphabets (σ, D) and (σ′, D′), it is decidable whether there exists a strong coding h: M(σ, D)→M(σ′, D′) between the associated trace monoids. In fact, we show that the problem is NP-complete. (A coding is an injective homomorphism, it is strong if independent letters are mapped to independent traces.) We exhibit an example of trace monoids where a coding between them exists, but no strong coding. The decidability of codings remains open, in general. We have a lower and an upper bound, which show both to be strict. We further discuss encodings of free products of trace monoids and give almost optimal constructions.In the final section, we state that the coding property is undecidable in a naturally arising class of homomorphisms.

We consider the problem of determining the largest tree embeddable in two labeled trees T and T′, where the embedding relation is one of subgraph isomorphism or topological embedding. This problem is a generalization of classical tree pattern matching where the problem is to determine if one labeled tree is isomorphic to a subgraph of another. In this paper, we present a general framework for the variations on the problem, for the two embedding relations and for different assumptions about labeling of nodes in the trees. Our general paradigm provides sequential and parallel algorithms for the various subproblems, many of which have no other known solutions.

Motivated by a problem in Scheduling Theory, we introduce the χt-coloring problem, a generalization of the chromatic number problem that places a bound of t on the size of any color class. For fixed t, we show that the perfect χt-coloring problem (in which each color class must have cardinality exactly t) can be expressed in the counting monadic second-order logic and, hence, has a linear-time algorithm over the class of graphs G of bounded treewidth: A solution is a partition of G into induced subgraphs, each isomorphic to a fixed graph consisting of t isolated vertices. The logical formalism generalizes to allow these t vertices to be t isomorphic connected components. The linear-time algorithm so derived for the perfect χt-coloring problem is used to design a linear-time algorithm for the optimization version of the general χt-coloring problem (for fixed t) on graphs of bounded treewidth. We also show that this problem has a polynomial-time algorithm on bipartite graphs.

Let H be an undirected graph. A random graph of type-H is obtained by selecting edges of H independently and with probability p. We can thus represent a communication network H in which the links fail independently and with probability f=1−p. A fundamental type of H is the clique of n nodes (leading to the well-known random graph G _n,p ). Another fundamental type of H is a random member of the set G _n d of all regular graphs of degree d (leading to a new type of random graphs, of the class G _n,p d). Note that G _n,p =G _n,p n−1. The G _n,p d model was introduced in ([11]).Information about the remaining (with high probability) structure of type-H random graphs is of interest to applications in reliable network computing. For example, it is well known that any member of G _n d is almost surely an efficient certifiable expander. Expanders are widely used in Computer Science. We have shown in ([11]) that G _n,p d has a giant component of small diameter even when d=O(1). We wish to determine the minimum value of p for which the giant component of G _n,p d remains a certifiable expander with high probability. In this paper we show that the second eigenvalue of the adjacency matrix of the giant component of G _n,p d is concentrated in an interval of small width around its mean, and that its mean is O((dp)3/4), provided that dp>256. Thus, the giant component of a random member of G _n,p d remains, with high probability, a certifiable efficient expander, despite the link faults, provided that dp>256.

We present a dynamic modelization of a database when submitted to a sequence of queries and updates, that allows us to study the evolution of the sizes of relations. While the problem of estimating the sizes of derived relations at a given time (“static” case) has been the subject of several studies, to the best of our knowledge the evolution of the relation sizes under queries and updates (“dynamic” cases) has not been studied so far. We consider the size of a relation as a random variable, and we study its probability distribution when the database is submitted to a sequence of insertions, deletions and queries. We show that it behaves asymptotically as a Gaussian process, whose expectation and covariance are proportional to the time. This approach also allows us to analyze the maximum of the size of the derived relation.

In this paper we study slender context-free languages, i.e., those containing at most a constant number of words of each length. Recently, Ilie proved that every such language can be described by a finite union of terms of the form uviwxiy [I]. We provide a completely different proof of this, using constructive methods. This enables us to prove that thinness and slenderness are decidable. Our proofs are based upon a novel characterization of languages in terms of the structure of the infinite paths in their prefix closure. This characterization seems to be interesting in itself, and can be expanded to more general families of languages.

We introduce a notion of a partial derivative of a regular expression. It is a generalization to the non-deterministic case of the known notion of a derivative invented by Brzozowski. We give a constructive definition of partial derivatives, study their properties, and employ them to develop a new algorithm for turning regular expressions into relatively small NFA and to provide certain improvements to Brzozowski's algorithm constructing DFA. We report on a prototype implementation of our algorithm constructing NFA and present some examples.

An automaton with concurrency relations A is a labeled transition system with a collection of binary relations indicating when two events in a given state of the automaton can happen independently from each other. The concurrency relations induce a natural equivalence relation for finite computation sequences. We investigate two graphtheoretic representations of the equivalence classes of computation sequences and obtain that under suitable assumptions on A they are isomorphic. Furthermore, the graphs are shown to carry a monoid operation reflecting precisely the composition of computations. This generalizes fundamental graph-theoretical representation results due to Mazurkiewicz in trace theory.

In this paper, we are interested in modelization of some aspects of massively parallel computers built by connecting together copies of a unique given pattern. Thus, a natural and important question arises. Is it possible to verify that a property holds, not for one given configuration, but for all the configurations that can be constructed? Of course, the difficulty comes from the fact that the number of distinct configurations is infinite. We focus in this paper on the deadlock problem: can we verify that any net, constructed by connecting an arbitrary number of copies of the pattern, is deadlock free? As in a great number of models, the semantics of the pattern and thus the semantics of a net are given by finite transition systems. The main result of this paper proves that the deadlock problem is surprisingly undecidable.

This paper is concerned with the average running time of Batcher's odd-even merge sort when implemented on a collection of processors. We consider the case where the size n of the input is an arbitrary multiple of the number p of processors used. We show that Batcher's odd-even merge (for two sorted lists of length m each) can be implemented to run in time O((m/p)(1+log(1+p2/m))) on the average, and that odd-even merge sort can be implemented to run in time O((n/p)(log(n/p)+logp(1+log(1+p2/n)))) on the average. In the case of merging (sorting) the average is taken over all possible outcomes of the merging (all possible permutations of n elements). That means that odd-even merge and odd-even merge sort have an optimal average running time if n≥p2.

We present algorithms for sorting and routing on two-dimensional mesh-connected parallel architectures that are optimal on average. If one processor has many packets then we asymptotically halve the up to now best running times. For a load of one optimal algorithms are known for the mesh. We improve this to a load of eight without increasing the running time. For tori no optimal algorithms were known even for a load of one. Our algorithm is optimal for every load. Other architectures we consider include meshes with diagonals and reconfigurable meshes. Furthermore, the method applies to meshes of arbitrary higher dimensions and also enables optimal solutions for the routing problem.

In [L90], Lutz proposed a notion of source, a nonrandom sequence that can substitute in a certain way for the random bits used by bounded-error probabilistic machines. He showed that almost every sequence in DSPACE(2Polynomial) is a source. We improve this abundance result to PSPACE, by first showing that the sources are exactly the classical normal numbers of Borel. We go on to show there are sources in AC0. Unfortunately, this suggests that alternate notions of source should be explored.

k-decision lists and decision trees play important roles in learning theory as well as in practical learning systems, k-decision lists generalize classes such as monomials, k-DNF, and k-CNF and like these subclasses is polynomially PAC-learnable [19]. This leaves open the question of whether k-decision lists can be learned as efficiently as k-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [2]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results.The following problems cannot be approximated in polynomial time within a factor of $$2^{\log ^\delta n}$$ for any δ<1, unless NP⊂DTIME[2polylog n]: a generalized set cover, k-decision lists, k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor of nδ, for some constant δ>0, unless NP=P. Also, k-decision lists with l 0–1 alternations cannot be approximated within a factor logln unless NP⊂DTIME[nO(log log n)] (providing an interesting comparison to the upper bound recently obtained in [1]).

Partitioning digital curves into digital straight line segments (DLS) is important in several branches of image processing. We present a parallel algorithm for this task which runs in O(log n) time using O(nlog2n) operations on a CREW PRAM. In contrast to earlier sequential algorithms it is not founded on number-theoretic properties of digital lines, instead we only use geometrical tools. The main observation for obtaining our complexity bounds is that the convex hull of a DLS of length n has O(log n) vertices. We also construct a sequence of DLS showing that this bound is tight.

We investigate computability of convex sets restricted to rational inputs. Several quite different algorithmic characterizations are presented, like the existence of effective approximations by polygons or effective line intersection tests. We also consider approximate computations of the n-fold characteristic function for several natural classes of convex sets. This yields many different concrete examples of (1, n)-computable sets.

We consider the problem of enumerating all extreme points of a given set P of n points in d dimensions. We present an algorithm with O(n) space and O(nm) time where m is the number of extreme points of P.We also present an algorithm to compute the depth of each point of the given set of n points in d-dimensions. This algorithm has complexity O(n2) which significantly improves the O(n3) complexity of the previously best known deterministic algorithm. It also improves the best known randomized algorithm which has a expected running time of $$O(n^{3 - \frac{2}{{1 + [d/2]}} + \delta } )$$ (for any fixed δ>0).

A solid object in 3-dimensional space may be described by a collection of all its topologically distinct 2-dimensional appearances, its aspect graph. In this paper, we study the complexity of aspect graphs of piecewise-smooth algebraic objects using the modern tools of algebraic geometry, i.e. intersection theory, multiple-point theory and enumerative geometry. We give a bound on the number of different appearances of such objects, an indication of the computational complexity of aspect graphs.

We investigate hierarchies of complexity classes defined by log-space probabilistic Turing machines, Arthur-Merlin games and Games against nature with logarithmic space-bounded probabilistic verifiers. We decompose each log-space complexity class into a hierarchy based on corresponding multihead two-way finite-state automata and we prove the separation of the levels of several hierarchies even over a one letter alphabet; furthermore, we show deterministic log-space reductions of each log-space complexity class to low levels of its corresponding hierarchy.We find probabilistic (and “probabilistic+nondeterministic”) variants of Savitch's maze threading problem that are log-space complete for PL (and respectively P) and that can be recognized by two-head one-way and one-head one-way one-counter finite-state automata with probabilistic (probabilistic and nondeterministic) states.

We prove the Instance Complexity Conjecture of Ko, Orponen, Schöning, and Watanabe for all recursive tally sets and for all recursive sets which are NP-hard under honest reductions, in particular it holds for all natural NP-hard problems. On the other hand, the conjecture is shown to be oracle dependent. Additional results concern the nonrecursiveness of the instance complexity measure and a comparison of time-bounded C- and CD-complexity.

We study the sparse set conjecture for sets with low density. The sparse set conjecture states that P=NP if and only if there exists a sparse Turing hard set for NP. In this paper we study a weaker variant of the conjecture. We are interested in the consequences of NP having Turing hard sets of density f(n), for (unbounded) functions f(n), that are sub-polynomial, for example log(n). We establish a connection between Turing hard sets for NP with density f(n) and bounded nondeterminism: We prove that if NP has a Turing hard set of density f(n), then satisfiability is computable in polynomial time with O(log(n)*f(nc)) many nondeterministic bits for some constant c. As a consequence of the proof technique we obtain absolute results about the density of Turing hard sets for EXP. We show that no Turing hard set for EXP can have sub-polynomial density. On the other hand we show that these results are optimal w.r.t. relativizing computations. For unbounded functions f(n), there exists an oracle relative to which NP has a f(n) dense Turing hard tally set but still P≠NP.

Buhrman and Torenvliet created an oracle relative to which PNP=NEXP and thus PNP=PNEXP. Their proof uses a delicate finite injury argument that leads to a nonrecursive oracle. We simplify their proof removing the injury to create a recursive oracle making PNP=NEXP. In addition, in our construction we can make P=UP=NP∩coNP. This leads to the curious situation where LOW(NP)=P but LOW(PNP)=NEXP, and the complete ≤ _m p-degree for PNP collapses to a p-isomorphism type.

In contrast to machine models like Turing machines or random access machines, circuits are a rigid computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, in complexity theory only worst case complexity measures have been used to analyse this model. In [JRS94] we have defined an average case measure for the time complexity of circuits. Using this notion tight upper and lower bounds could be obtained for the average case complexity of several basic Boolean functions.In this paper we will examine the asymptotic average case complexity of the set of n-input Boolean functions. In contrast to the worst case a simple counting argument does not work. We prove that almost all Boolean function require at least n— log n— log n expected time even for the uniform probability distribution. On the other hand, we show that there are significant subsets of functions that can be computed with a constant average delay.Finally, the worst case and average case complexity of a Boolean function will be compared. We show that for each function that requires circuit depth d, the expected time complexity will be at least d— log n— log d with respect to an explicitely defined probability distribution. A nontrivial bound on the complexity of such a distribution is obtained.

In order to analyse the genetic code, the distribution of the 64 trinucleotides w (words of 3 letters on the gene alphabet {A,C,G,T}, w∈τ={AAA,⋯,TTT}) in the prokaryotic protein coding genes (words of large sizes) is studied with autocorrelation functions. The trinucleotides wp can be read in 3 frames p (p=0: reference frame, p=1: reference frame shifted by 1 letter, p=2: reference frame shifted by 2 letters) in coding genes. Then, the autocorrelation function wp(N)_iw′ analyses the occurrence probability of the i-motif wp(N)_iw′, i.e. 2 trinucleotides wp in frame p and w′ in any frame (w,w′∈ τ) which are separated by any i bases N (N=A, C, G or T). The 642×3=12288 autocorrelation functions applied to the prokaryotic protein coding genes are almost all non-random and have a modulo 3 periodicity among the 3 following types: 0 modulo 3, 1 modulo 3 and 2 modulo 3. The classification of 12288 i-motifs wp(N)_iw′ according to the type of periodicity implies a constant preferential occurrence frame for w′ independent of w and p. Three sub-sets of trinucleotides are identified: 22 trinucleotides in frame 0 forming the subset τ₀={AAA, AAC, AAT, ACC, ATC, ATT, CAG, CTC, CTG, GAA, GAC, GAG, GAT, GCC, GGC, GGT, GTA, GTC, GTT, TAC, TTC, TTT} and 21 trinucleotides in each of the frames 1 and 2 forming the sub-sets τ₁ and τ₂ respectively. Except for AAA, CCC, GGG and TTT, the sub-sets τ₁ and τ₂ are generated by a circular permutation P of τ₀: P(τ₀)=τ₁ and P(τ₁)=τ₂. Furthermore, the complementarity property ∁ of the DNA double helix (i.e. ∁(A)=T, ∁(C)=G, ∁(G)=C, ∁(T)=A and if w=l₁l₂l₃ then ∁(w)=∁(l₃)∁(l₂)∁(l₁) with l₁, l₂, l₃∈{A,C,G,T}) is observed in these 3 sub-sets: ∁(τ₀)=τ₀, ∁(τ₁)=τ₂ and ∁(τ₂)=τ₁.