A1 Refereed original research article in a scientific journal
Unambiguous finite automata over a unary alphabet
Authors: Okhotin A
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2012
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Volume: 212
First page : 15
Last page: 36
Number of pages: 22
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2012.01.003
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) 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.
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.
UTU Research Portal