Narrow Results

Partial word finite automata are deterministic finite automata that may have state transitions on a special symbol ◇ which represents an unknown symbol or a hole in the word. Together with a subset of the input alphabet that gives the symbols which may be substituted for the ◇, a partial word finite automaton represents a regular language. However, this substitution implies a certain form of limited nondeterminism in the computations when the ◇-transitions are replaced by ordinary transitions. In this paper we first reconsider the problem to prove the minimality of partial word finite automata and present a method to utilize minimal $\mathrm{\text{NFA}}$s with certain properties for this purpose. Then we study the operational state complexity of partial word finite automata with respect to Boolean operations. It turns out that the upper and lower bounds for all these operations are exponential. Moreover, we establish state complexity hierarchies on the number of productive ◇-transitions that may appear in partial word finite automata for general and unary regular languages. In the general case, the levels of the hierarchy are separated by exponential state costs, whereas in the unary case the levels are separated by quadratic state costs.

We design Latvian quantum finite state automata (LQFAs) recognizing unary regular languages with isolated cut point $\frac{1}{2}$. From an architectural viewpoint, we suitably combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language $L$ consists of. In particular, both these LQFAs incorporate a sub-module discriminating strings on the basis of their length.

Both the number of basis states and the isolation around the cut point of the resulting LQFAs for $L$ exponentially depend on the size of the minimal deterministic finite state automaton for $L$. Moreover, the recognition of $L$ tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows.

In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.

Conjunctive grammars, introduced by Okhotin, extend context-free grammars by an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Okhotin posed nine open problems concerning those grammars. One of them was a question, whether a conjunctive grammars over a unary alphabet generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language {a⁴ⁿ : n ∈ ℕ}. We also generalize this result: for every set of natural numbers L we show that {aⁿ : n ∈ L} is a conjunctive unary language, whenever the set of representations in base-k system of elements of L is regular, for arbitrary k.

The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states that is exponential in s. We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly smaller than the number of variables needed in the case of nonunary alphabets.

Systems of equations of the form X = Y + Z and X = C, in which the unknowns are sets of natural numbers, "+" denotes elementwise sum of sets S + T = {m + n | m ∈ S, n ∈ T}, and C is an ultimately periodic constant, have recently been proved to be computationally universal (Jeż, Okhotin, "Equations over sets of natural numbers with addition only", STACS 2009). This paper establishes some limitations of such systems. A class of sets of numbers that cannot be represented by unique, least or greatest solutions of systems of this form is defined, and a particular set in this class is constructed. The argument is then extended to equations over sets of integers.

We investigate the descriptional complexity of deterministic one-way multi-head finite automata accepting unary languages. It is known that in this case the languages accepted are regular. Thus, we study the increase of the number of states when an n-state k-head finite automaton is simulated by a classical (one-head) deterministic or nondeterministic finite automaton. In the former case upper and lower bounds that are tight in the order of magnitude are shown. For the latter case we obtain an upper bound of O(n^2k) and a lower bound of Ω(n^k) states. We investigate also the costs for the conversion of one-head nondeterministic finite automata to deterministic k-head finite automata, that is, we trade nondeterminism for heads. In addition, we study how the conversion costs vary in the special case of finite and, in particular, of singleton unary lanuages. Finally, as an application of the simulation results, we show that decidability problems for unary deterministic k-head finite automata such as emptiness or equivalence are LOGSPACE-complete.

The investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case (Ginsburg and Rice, 1962). Many differences have been proved concerning the state costs of the simulations between different variants of unary finite state automata (Chrobak, 1986, Mereghetti and Pighizzini, 2001). We present an overview of these results. Because important connections with fundamental questions in space complexity, we give emphasis to unary two-way automata. Furthermore, we discuss unary versions of other computational models, as probabilistic automata, one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata.

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak log n space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong log log n space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle log n space and bounded error.