# 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].

##### MSC:
 68Q45 Formal languages and automata
Full Text: