## Abstract

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 language | English |
---|---|

Pages (from-to) | 15-36 |

Number of pages | 22 |

Journal | Information and Computation |

Volume | 212 |

DOIs | |

Publication status | Published - 1 Mar 2012 |

## Scopus subject areas

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