Real-time recognition of two-dimensional tapes by cellular automata

We introduce an n-dimensional cellular automaton (n-BCA) which accepts (n + 1)-dimensional tapes in real time. Here we regard an (n + 1)-dimensional tape as a time sequence of n-dimensional tapes, and we say that an (n + 1)-dimensional tape is accepted by an n-BCA if a final-state configuration of the acceptor belongs to a predetermined set of n-dimensional words. We state some features of the sets of 2-dimensional tapes accepted by deterministic 1-BCA's (1-DBCA's), including closure properties. For the unary input alphabet, we obtain that 1-DBCA's can recognize every set of tapes each of which has length represented by a polynomial in its width. For an arbitrary input alphabet, we obtain that the class of languages each of which consists of all the ith rows of 2-dimensional tapes accepted by a 1-DBCA coincides with the class of context-sensitive languages. For n ? 2, we show that a language not containing the empty word is recursively enumerable if and only if it is the set of top rows of (n + 1)-dimensional tapes accepted by an n-DBCA.     

On tape bounds for single letter alphabet language processing

In this paper we show that the tape bounded complexity classes of languages over single letter alphabets (sla) are closed under complementation. We then use this results to show by means of diagonalization that there exists an infinite hierarchy of tape bounded complexity classes of sla languages between log log n and log n tape bounds. On the other hand, we show that the power of diagonalization over sla inputs with less than log n tape is very limited by proving that every infinite sla language accepted using less than log n tape contains infinite regular subsets. From this result it immediately follows that the set of primes in unary notation, P, requires exactly log n tape for its recognition and every infinite subset of P requires at least log n tape.     

Stabbing c-oriented polygons

Given a point and a set of objects in 2-space, the point's stabbing number is the number of objects in the set enclosing it. We introduce the notion of c-oriented objects, that is, objects whose edges are oriented in only a constant number of previously defined directions. We devise time-optimal algorithms for determining the stabbing numbers of points with respect to a set of c-oriented polygons: Given a mixed set of points and polygons of size n we show how to determine the stabbing numbers of all points in O(n log n) time. For a static set of polygons we are able to answer stabbing number queries in O(log n) time. For the second problem the same time bound was achieved previously, but only with much higher space- and preprocessing-costs.     

Beeping a maximal independent set

We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in $\mathcal O (\log ^3 n)$ time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in $\mathcal O (\log ^3 n)$ time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in $\mathcal O (\log ^2 n)$ time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in $\mathcal O (\log ^2 n)$ time.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

Stack languages and log n space

We consider the space complexity of stack languages. The main result is: if a language is accepted by a deterministic (nondeterministic) one-way stack automaton then it is the image under a nonerasing homomorphism of a language accepted by a deterministic (nondeterministic) Turing machine that operates within space log n.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

On the power of 1-tape off-line ATMs running in a bounded number of reversals

It is known that 1-tape-1-counter alternating Turing machines (ATMs) making a constant number of reversals recognize all recursively enumerable languages. Yamamoto and Noguchi raised the question whether 1-tape off-line ATMs with a constant reversal bound have the same computational power. Recently, Jiang has given a negative answer to this question by defining a recursive functionh(s,r,n) such that, for everys-state 1-tape off-line ATMM running inr reversals, the language accepted byM is inASPACE(h(s, r, n)). In this paper we continue the investigation of the reversal complexity of 1-tape off-line ATMs. We improve the result of Jiang showing that the functionh can be reduced to a functionf(s, r, n) log log log logh(s,r,n). We also prove that 1-tape off-line ATMs recognize only recursive languages even if an arbitrary recursive bound (instead of only a constant) on the number of reversals is set. We conclude the paper by giving an astonishing reversal hierarchy theorem for the machines considered.This research was supported by the Alexander-von-Humboldt-Stiftung while the author was visiting the Institut für Theoretische Informatik, TH Darmstadt, 6100 Darmstadt, Germany.     

EOL languages are not codings of FPOL languages

One of the useful results concerning EOL languages states that a language is an EOL language if and only if it is a cording of OL language. In this paper we retine this result by demonstrating that there exist EOL languages that are not codings of languages that are generated by propagating OL systems with finite axiom sets. This solves Problem 10 from the L Systems Problem Book '75.     

A parallel median algorithm

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)²) parallel time on O(n) processors in Valiant's comparison model.     

Transducer generated arrays of robotic nano-arms

We consider sets of two-dimensional arrays, called here transducer generated languages, obtained by iterative applications of transducers (finite state automata with output). Each transducer generates a set of blocks of symbols such that the bottom row of a block is an input string accepted by the transducer and, by iterative application of the transducer, each row of the block is an output of the transducer on the preceding row. We show how these arrays can be implemented through molecular assembly of triple crossover DNA molecules. Such assembly could serve as a scaffold for arranging molecular robotic arms capable of simultaneous movements. We observe that transducer generated languages define a class of languages which is a proper subclass of recognizable picture languages, but it contains the class of all factorial local two-dimensional languages. By taking the average growth rate of the number of blocks in the language as a measure of its complexity, we further observe that arrays with high complexity patterns can be generated in this way.     

Constraint hierarchies

Constraints allow programmers and users to state declaratively a relation that should be maintained, rather than requiring them to write procedures to maintain the relation themselves. They are thus useful in such applications as programming languages, user interface toolkits, and simulation packages. In many situations, it is desirable to be able to state bothrequired andpreferential constraints. The required constraints must hold. Since the other constraints are merely preferences, the system should try to satisfy them if possible, but no error condition arises if it cannot. Aconstraint hierarchy consists of a set of constraints, each labeled as either required or preferred at some strength. An arbitrary number of different strengths is allowed. In the discussion of a theory of constraint hierarchies, we present alternate ways of selecting among competing possible solutions, and prove a number of propositions about the relations among these alternatives. We then outline algorithms for satisfying constraint hierarchies, and ways in which we have used constraint hierarchies in a number of programming languages and systems.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Constraint hierarchies

Constraints allow programmers and users to state declaratively a relation that should be maintained, rather than requiring them to write procedures to maintain the relation themselves. They are thus useful in such applications as programming languages, user interface toolkits, and simulation packages. In many situations, it is desirable to be able to state bothrequired andpreferential constraints. The required constraints must hold. Since the other constraints are merely preferences, the system should try to satisfy them if possible, but no error condition arises if it cannot. Aconstraint hierarchy consists of a set of constraints, each labeled as either required or preferred at some strength. An arbitrary number of different strengths is allowed. In the discussion of a theory of constraint hierarchies, we present alternate ways of selecting among competing possible solutions, and prove a number of propositions about the relations among these alternatives. We then outline algorithms for satisfying constraint hierarchies, and ways in which we have used constraint hierarchies in a number of programming languages and systems.     

Relativizations for the Logic-Automata Connection

BDDs and their algorithms implement a decision procedure for Quantified Propositional Logic. BDDs are a kind of acyclic automata. But unrestricted automata (recognizing unbounded strings of bit vectors) can be used to decide monadic second-order logics, which are more expressive. Prime examples are WS1S, a number-theoretic logic, or the string-based logical notation of introductory texts. One problem is that it is not clear which one is to be preferred in practice. For example, it is not known whether these two logics are computationally equivalent to within a linear factor, that is, whether a formula ϕ of one logic can be transformed to a formula %phis;′ of the other such that %phis;′ is true if and only if ϕ is and such that ϕ′ is decided in time linear in that of the time for ϕ.Another problem is that first-order variables in either version are given automata-theoretic semantics according to relativizations, which are syntactic means of restricting the domain of quantification of a variable. Such relativizations lead to technical arbitrations that may involve normalizing each subformula in an asymmetric manner or may introduce spurious state space explosions.In this paper, we investigate these problems through studies of congruences on strings. This algebraic framework is adapted to language-theoretic relativizations, where regular languages are intersected with restrictions. The restrictions are also regular languages. We introduce ternary and sexpartite characterizations of relativized regular languages. From properties of the resulting congruences, we are able to carry out detailed state space analyses that allow us to address the two problems.We report briefly on practical experiments that support our results. We conclude that WS1S with first-order variables can be robustly implemented in a way that efficiently subsumes string-based notations.Dedicated to the memory of Bob Paige and his contributions to automata algorithmsSome of the material in this paper appeared in Computer Aided Verification, CAV ‘99, LNCS 1633, 1999, under the title “A theory of restrictions for logics and automata.” This work was carried out while the author was with AT&T Labs–Research; itwas also supported in part by grant CCR-0341658 from the National Science Foundation.     

Fast language acceptance by shrinking cellular automata

When bounded cellular automata are used as acceptors for formal languages, the number of time steps required to accept a string σ is at least ¦σ¦, except in certain trivial cases, since the distinguished cell's state after t steps cannot depend on the initial states of the cells at distances > t from it. However, if the automaton is allowed to shrink (i.e., cells are deleted, and their predecessors become directly connected to their successors), language acceptance in less than linear time becomes possible.     

On inverse deterministic pushdown transductions

Classes of source languages which can be mapped by a deterministic pushdown (DPDA) transduction into a given object language (while their complement is mapped into the complement of the object language) are studied. Such classes of source languages are inverse DPDA transductions of the given object language. Similarly for classes of object languages. The inverse DPDA transductions of the Dyck sets are studied in greater detail: they can be recognized in deterministic storage (log n)' but do not comprise all context free languages; their emptiness problem is unsolvable and their closure under homomorphism constitutes the r.e. sets. For each object language L we can exhibit a storage hardest language for the class of inverse DPDA transductions of L; similarly for the classes of regular, deterministic context free, and context free object languages. Last, we classify the classes of inverse DPDA transductions of the regular, deterministic context free, context free and deterministic context sensitive languages.     

Context-free languages can be accepted with absolutely no space overhead

We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits’ own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such overhead-free machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.     

The complexity of ranking simple languages

Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1-way unambiguous auxiliary pushdown automata operating in polynomial time is inNC ⁽²⁾. We also prove negative results about ranking for several classes of simple languages.C is rankable in deterministic polynomial time iffP=P ^#P , whereC is any of the following six classes of languages: (1) languages accepted by logtime-bounded nondeterministic Turing machines, (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size, (3) languages accepted by 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1-way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.This research was partially supported by the National Science Foundation under Grant DCR-8696097. A preliminary version of this paper was presented at the 3rd Annual Structure in Complexity Theory Conference, Washington, DC, June 1988.     

Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by n-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary d-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log² d, not even in the best case.