Alexander Okhotin:
A Study of Unambiguous Finite Automata Over a One-Letter Alphabet
ISBN: 978-952-12-2328-0
TechreportLanguage: English
Year: 2009
Month: Sep
Series: Technical Reports
Number: 951
Institution: TUCS
Keywords: Finite automata, unary languages, ambiguity, descriptional complexity, state complexity, Landau's function
Laboratory: Discrete Mathematics for Information Technology
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.
Download full text
