Unambiguous finite automata over a unary alphabet

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 one-letter alphabet, and determines the exact number of states in DFAs needed to represent unary languages recognized by n-state UFAs in terms of a new number-theoretic function . The growth rate of , and therefore of the UFA–DFA tradeoff, is estimated as . The conversion of an n-state unary NFA to a UFA requires UFAs with states, where g(n) is the greatest order of a permutation of n elements, known as Landauʼs function. In addition, it is shown that representing the complement of n-state unary UFAs requires UFAs with at least n2−o(1) states in the worst case, while the Kleene star requires up to exactly 2(n−1)+1 states.