State complexity of union and intersection for two-way nondeterministic finite automata

Michal Kunc, Alexander Okhotin

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

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


The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m+n and at most m+n+1. For the union operation, the number of states is exactly m+n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n ≥ 2 with m, n ≠ 6 (and with finitely many other exceptions), there exist partitions m = p1 +⋯+ pk and n = q1 +⋯+ql, where all numbers p1,⋯ , pk, q1,⋯ , ql ≥ 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n ∉ {4, 6} (with a few more exceptions) into sums of pairwise distinct primes is established as well.

Язык оригиналаанглийский
Страницы (с-по)231-239
Число страниц9
ЖурналFundamenta Informaticae
Номер выпуска1-4
СостояниеОпубликовано - 20 сен 2011

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

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

Fingerprint Подробные сведения о темах исследования «State complexity of union and intersection for two-way nondeterministic finite automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).