zbMATH — the first resource for mathematics

Unambiguous finite automata over a unary alphabet. (English) Zbl 1287.68098
Hliněný, Petr (ed.) et al., Mathematical foundations of computer science 2010. 35th international symposium, MFCS 2010, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15154-5/pbk). Lecture Notes in Computer Science 6281, 556-567 (2010).
Summary: Nondeterministic finite automata (NFA) with at most one accepting computation on every input string are known as unambiguous finite automata (UFA). This paper considers UFAs over a unary alphabet, and determines the exact number of states in DFAs needed to represent unary languages recognized by \(n\)-state UFAs: the growth rate of this function is \(e^{\Theta(\root 3 \of{n \ln^2 n})}\). The conversion of an \(n\)-state unary NFA to a UFA requires UFAs with \(g(n)+O(n^2)=e^{\sqrt{n \ln n}(1+o(1))}\) states, where \(g(n)\) is Landau’s function. In addition, it is shown that the complement of \(n\)-state unary UFAs requires up to at least \(n^{2 - o(1)}\) states in an NFA, while the Kleene star requires up to exactly \((n - 1)^{2} + 1\) states.
For the entire collection see [Zbl 1194.68039].

68Q45 Formal languages and automata
Full Text: DOI