Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Study of Unambiguous Finite ...

A Study of Unambiguous Finite Automata Over a One-Letter Alphabet

Alexander Okhotin, A Study of Unambiguous Finite Automata Over a One-Letter Alphabet. TUCS Technical Reports 951, Turku Centre for Computer Science, 2009.

Abstract:

Nondeterministic finite automata (NFA) with at most one accepting computation on every input string are known as unambiguous finite automata (UFA). It is shown that every UFA over a unary alphabet $\Sigma=\{a\}$ can be transformed to the Chrobak normal form without adding any extra states. The normal form is then used to determine 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(\sqrt[3]{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 at least $n^{2-o(1)}$ states in an NFA.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin09a,
  title = {A Study of Unambiguous Finite Automata Over a One-Letter Alphabet},
  author = {Okhotin, Alexander},
  number = {951},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2009},
  keywords = {Finite automata, unary languages, ambiguity, descriptional complexity, state complexity, Landau's function},
  ISBN = {978-952-12-2328-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication