Unambiguous finite automata over a unary alphabet

: Okhotin A

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2012

: Information and Computation

: INFORMATION AND COMPUTATION

: INFORM COMPUT

: 212

: 15

: 36

: 22

: 0890-5401

DOI: https://doi.org/10.1016/j.ic.2012.01.003

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 (g) over tilde. The growth rate of (g) over tilde (n), and therefore of the UFA-DFA tradeoff, is estimated as e(Theta(3 root n vertical bar n2n)). The conversion of an n-state unary NFA to a UFA requires UFAs with g(n) + O(n(2)) = e((1 + o(1))root n vertical bar n n) 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 n(2-o(1)) states in the worst case, while the Kleene star requires up to exactly (n - 1)(2) + 1 states. (C) 2012 Elsevier Inc. All rights reserved.