Standard

Unambiguous finite automata over a unary alphabet. / Okhotin, Alexander.

In: Information and Computation, Vol. 212, 01.03.2012, p. 15-36.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A 2012, 'Unambiguous finite automata over a unary alphabet', Information and Computation, vol. 212, pp. 15-36. https://doi.org/10.1016/j.ic.2012.01.003

APA

Okhotin, A. (2012). Unambiguous finite automata over a unary alphabet. Information and Computation, 212, 15-36. https://doi.org/10.1016/j.ic.2012.01.003

Vancouver

Okhotin A. Unambiguous finite automata over a unary alphabet. Information and Computation. 2012 Mar 1;212:15-36. https://doi.org/10.1016/j.ic.2012.01.003

Author

Okhotin, Alexander. / Unambiguous finite automata over a unary alphabet. In: Information and Computation. 2012 ; Vol. 212. pp. 15-36.

BibTeX

@article{7731d937933e4e808346f9f72b7a1ff2,
title = "Unambiguous finite automata over a unary alphabet",
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.",
keywords = "Ambiguity, Descriptional complexity, Finite automata, Landau's function, State complexity, Unary languages",
author = "Alexander Okhotin",
year = "2012",
month = mar,
day = "1",
doi = "10.1016/j.ic.2012.01.003",
language = "English",
volume = "212",
pages = "15--36",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Unambiguous finite automata over a unary alphabet

AU - Okhotin, Alexander

PY - 2012/3/1

Y1 - 2012/3/1

N2 - 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.

AB - 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.

KW - Ambiguity

KW - Descriptional complexity

KW - Finite automata

KW - Landau's function

KW - State complexity

KW - Unary languages

UR - http://www.scopus.com/inward/record.url?scp=84857261182&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2012.01.003

DO - 10.1016/j.ic.2012.01.003

M3 - Article

AN - SCOPUS:84857261182

VL - 212

SP - 15

EP - 36

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -

ID: 41139943