The complexity of restricted regular expressions and the synthesis problem for finite automata

It is known that for every restricted regular expression of length n there exists a nondeterministic finite automaton with n + 1 states giving rise to the upper bound of 2ⁿ + 1 on the number of states of the corresponding reduced automaton. In this note we show that this bound can be attained for all n ? 2, i.e., the upper bound 2ⁿ + 1 is optimal. An observation is then made about the synthesis problem for nondeterministic finite automata.     

A tighter analysis of Piterman's Büchi determinization

Determinization and complementation are two fundamental problems in automata theory. Very recently, Piterman improved Safra's determinization and, presented a new construction which produces parity automata with a smaller size. We give a tighter analysis on that determinization construction and show that the number of states of the resulting deterministic automaton is bounded by 2n²(n!) instead of 2n!nn.     

Two heads are better than one

A class of multihead automata in which the heads operate in parallel is defined. Deterministic two-head automata are described that accept the languages aⁿbⁿ (or, more generally, the strings on a,b having the same number of a's as b's; and similarly for aⁿbⁿcⁿ, etc.); ww; ww^R; and a^kn, for any fixed k.     

Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n⁸)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n⁸) states.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata

For each sufficiently large n, there exists a unary regular language L such that both L and its complement L ^c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least \(e^{\Omega(\sqrt[3]{n\cdot\ln^{2}n})}\). Actually, L and L ^c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.     

Unbounded-error quantum computation with small space bounds

We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilistic Turing machines for any common space bound s satisfying s(n)=o(loglogn). For “one-way” Turing machines, where the input tape head is not allowed to move left, the above result holds for s(n)=o(logn). We also give a characterization for the class of languages recognized with unbounded error by real-time quantum finite automata (QFAs) with restricted measurements. It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Unlike the case with classical finite automata, when the QFA tape head is allowed to remain stationary in some steps, more languages become recognizable. We define and use a QTM model that generalizes the other variants introduced earlier in the study of quantum space complexity.     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

Deciding word neighborhood with universal neighborhood automata

Given some form of distance between words, a fundamental operation is to decide whether the distance between two given words w and v is within a given bound. In earlier work, we introduced the concept of a universal Levenshtein automaton for a given distance bound n. This deterministic automaton takes as input a sequence χ of bitvectors computed from w and v. The sequence χ is accepted iff the Levenshtein distance between w and v does not exceed n. The automaton is called universal since the same automaton can be used for arbitrary input words w and v, regardless of the underlying input alphabet. Here, we extend this picture. After introducing a large abstract family of generalized word distances, we exactly characterize those members where word neighborhood can be decided using universal neighborhood automata similar to universal Levenshtein automata. Our theoretical results establish several bridges to the theory of synchronized finite-state transducers and dynamic programming. For small neighborhood bounds, universal neighborhood automata can be held in main memory. This leads to very efficient algorithms for the above decision problem. Evaluation results show that these algorithms are much faster than those based on dynamic programming.     

Cellular automata with limited inter-cell bandwidth

A d-dimensional cellular automaton is a d-dimensional grid of interconnected interacting finite automata. There are models with parallel and sequential input modes. In the latter case, the distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature this model is referred to as an iterative array. In this paper, d-dimensional iterative arrays and one-dimensional cellular automata are investigated which operate in real and linear time and whose inter-cell communication bandwidth is restricted to some constant number of different messages independent of the number of states. It is known that even one-dimensional two-message iterative arrays accept rather complicated languages such as {a^p∣p prime} or {a²ⁿ∣n∈N} (H. Umeo, N. Kamikawa, Real-time generation of primes by a 1-bit-communication cellular automaton, Fund. Inform. 58 (2003) 421-435). Here, the computational capacity of d-dimensional iterative arrays with restricted communication is investigated and an infinite two-dimensional hierarchy with respect to dimensions and messages is shown. Furthermore, the computational capacity of the one-dimensional devices in question is compared with the power of two-way and one-way cellular automata with restricted communication. It turns out that the relations between iterative arrays and cellular automata are quite different from the relations in the unrestricted case. Additionally, an infinite strict message hierarchy for real-time two-way cellular automata is obtained as well as a very dense time hierarchy for k-message two-way cellular automata. Finally, the closure properties of one-dimensional iterative arrays with restricted communication are investigated and differences to the unrestricted case are shown as well.     

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.     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Morphismes et bimorphismes d'arbres

For every pair of positive integers n and p, there is a language accepted by a real-time deterministic pushdown automaton with n states and p stack symbols and size O(np), for which every context-free grammar needs at least n²p+1 nonterminals if n>1 (or p non-terminals if n = 1). It follows that there are context-free languages which can be recognized by pushdown automata of size O(np), but which cannot be generated by context-free grammars of size smaller than O(n²p); and that the standard construction for converting a pushdown automaton to a context-free grammar is optimal in the sense that it infinitely often produces grammars with the fewest number of nonterminals possible.     

Complexity results for classes of quantificational formulas

We analyze the computational complexity of determining whether F is satisfiable when F is a formula of the classical predicate calculus obeying certain syntactic restrictions. For example, for the monadic predicate calculus and the Gödel or 3 … ???? … 3 prefix class we obtain lower and upper nondeterministic time bounds of the form c^{n/log n}. The lower bounds are established by using acceptance problems for time-bounded Turing machines and alternating pushdown and stack automata.     

An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps

We present a symbolic algorithm for strongly connected component decomposition. The algorithm performs Θ(n log n) image and preimage computations in the worst case, where n is the number of nodes in the graph. This is an improvement over the previously known quadratic bound. The algorithm can be used to decide emptiness of Büchi automata with the same complexity bound, improving Emerson and Lei's quadratic bound, and emptiness of Streett automata, with a similar bound in terms of nodes. It also leads to an improved procedure for the generation of nonemptiness witnesses. This work was supported in part by SRC contract 98-DJ-620 and NSF grant CCR-99-71195. This work was done while the author was at the University of Colorado at Boulder.     

A lower bound on the area of permutation layouts

In this paper we prove a tight Ω(n ³) lower bound on the area of rectilinear grids which allow a permutation layout ofn inputs andn outputs. Previously, the best lower bound for the area of permutation layouts with arbitrary placement of the inputs and outputs was Ω(n ²), though Cutler and Shiloach [CS] proved an Ω(n ^2.5) lower bound for permutation layouts in which the set of inputs and the set of outputs each lie on horizontal lines. Our lower bound also holds for permutation layouts in multilayer grids as long as a fixed fraction of the paths do not change layers.     

The firing squad synchronization problem for a class of polyautomata networks

By the work of Rosenstiehl we know that the firing squad synchronization problem for the class of all polyautomata networks N satisfying the following conditions has a solution: (1) N is connected, (2) the connections of N are bilateral (that is, each connection carries information in both directions). We show that the problem has a solution even if we delete condition (2) if we add the following conditions: (3) the “fan-out” of each output terminal of automata is at most one, (4) for each output terminal of an automaton, the automaton knows whether there is a connection from the output terminal or not. The firing time of our solution is at most (2a2 + 1)ⁿ for sufficiently large n (n is the number of finite automata in the given network and a is the number of output terminals of the component finite automaton).     

Counting the number of games

We give upper and lower bounds on g(n) equal to the number of games born by day n. In particular, we give an upper bound of g(n+1)⩽g(n)+2^g(n)+2. For the lower bound, for all α<1, for sufficiently large n, g(n+1)⩾2^g(n)α.     

Fooling a two-way nondeterministic multihead automaton with reversal number restriction

Summary We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with n ^a reversal bound, where n is the length of input words, and 1/3>a>0 is a real number. Since L is recognized by a two-way deterministic two-head finite automaton working in linear time we obtain, for two-way finite automata, that time, reading heads, and nondeterminism as resources cannot compensate for the reversal number restriction.This work was supported as a part of the SPZV I-1-5/8 grant     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.