A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Unambiguous finite automata over a unary alphabet
Tekijät: Okhotin A
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2012
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 212
Aloitussivu: 15
Lopetussivu: 36
Sivujen määrä: 22
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2012.01.003
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali