Unambiguous finite automata over a unary alphabet

Результат исследований: Научные публикации в периодических изданияхстатья

22 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)15-36
Число страниц22
ЖурналInformation and Computation
Том212
DOI
СостояниеОпубликовано - 1 мар 2012

Предметные области Scopus

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

Fingerprint Подробные сведения о темах исследования «Unambiguous finite automata over a unary alphabet». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать