TY - JOUR

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

AU - Kunc, Michal

AU - Okhotin, Alexander

PY - 2011/9/20

Y1 - 2011/9/20

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

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

KW - Finite automata

KW - partitions into sums of primes

KW - state complexity

KW - two-way automata

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

U2 - 10.3233/FI-2011-540

DO - 10.3233/FI-2011-540

M3 - Article

AN - SCOPUS:80052786615

VL - 110

SP - 231

EP - 239

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-4

ER -