Search

For a formal language L , the problem of language enumeration asks to compute the length-lexicographically smallest word in L larger than a given input w ∈ Σ ∗ (henceforth called the L -successor of w). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute L -successors. As a byproduct, we obtain that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are sufficient for a DFA to recognize the subset S (L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S (L) is represented as an NFA. It has been known that L -successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in N L. If the regular language L is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of L under D L O G T I M E -uniform A C 0 reductions. In particular, this implies that fixed star-free languages can be enumerated in A C 0 , arbitrary fixed regular languages can be enumerated in N C 1 and that there exist regular languages for which the problem is N C 1 -complete. [ABSTRACT FROM AUTHOR]

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 2 5 is the sum of at most three natural numbers whose base- 2 representation has an equal number of 0 's and 1 's. [ABSTRACT FROM AUTHOR]

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. Ifxandyare compositions, we sayxis equivalent toyif they have the same effect on all languagesL. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any languageLunder the elements of the monoid is finite and bounded, independent ofL. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [ABSTRACT FROM AUTHOR]

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. [ABSTRACT FROM AUTHOR]

A famous theorem of Kuratowski states that, in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a given set. We re-examine this theorem in the setting of formal languages, where by "closure" we mean either Kleene closure or positive closure. We classify languages according to the structure of the algebras they generate under iterations of complement and closure. There are precisely 9 such algebras in the case of positive closure, and 12 in the case of Kleene closure. We study how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words do not commute. We can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete. [ABSTRACT FROM AUTHOR]

Abstract: The cross-section enumeration problem is to list all words of length in a regular language in lexicographical order. The enumeration problem is to list the first words in according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in , where is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable. [Copyright &y& Elsevier]

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity point of view. In particular, we give optimal upper bounds for the number of states of nondeterministic and deterministic finite automata equivalent to unary context-free grammars in Chomsky normal form. These bounds are functions of the number of variables of the given grammars. We also give upper bounds for the number of states of finite automata simulating unary pushdown automata. As a main consequence, we are able to prove a log log n lower bound for the workspace used by one-way auxiliary pushdown automata in order to accept nonregular unary languages. The notion of space we consider is the so-called weak space concept. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD (L) in L ⁎ that have unique factorization over L. We also consider similar notions for weaker forms of unique decipherability, such as numerically decipherable words ND (L) , multiset decipherable words MSD (L) and set decipherable words SD (L). Although these notions of unique factorization have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up until now. We show that UD (L) , ND (L) , MSD (L) and SD (L) need not be context-free if L is context-free. In fact ND (L) and MSD (L) need not be context-free even if L is finite, although UD (L) and SD (L) are regular in this case. We show that if L is context-sensitive, then so are UD (L) , ND (L) , MSD (L) and SD (L). We also prove that the membership problem (resp., emptiness problem) for these classes is PSPACE-complete (resp., undecidable). We finally determine upper and lower bounds on the length of the shortest word of L ⁎ not having the various forms of unique decipherability into elements of L. [ABSTRACT FROM AUTHOR]

Abstract: Let the words of a language be arranged in increasing radix order: . We consider transformations that extract terms from in an arithmetic progression. For example, two such transformations are and . Lecomte and Rigo observed that if is regular, then so are , , and analogous transformations of . We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language such that is not context-free. [Copyright &y& Elsevier]