DOI

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∼. The growth rate of g∼(n), and therefore of the UFA-DFA tradeoff, is estimated as eΘ(n ln2 n3). The conversion of an n-state unary NFA to a UFA requires UFAs with g(n)+O( n2 )=e( 1+o(1))nlnn 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 ( n-1)2 +1 states.

Original languageEnglish
Pages (from-to)15-36
Number of pages22
JournalInformation and Computation
Volume212
DOIs
StatePublished - 1 Mar 2012

    Research areas

  • Ambiguity, Descriptional complexity, Finite automata, Landau's function, State complexity, Unary languages

    Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

ID: 41139943