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

Standard

State complexity of union and intersection for two-way nondeterministic finite automata. / Kunc, Michal; Okhotin, Alexander.

In: Fundamenta Informaticae, Vol. 110, No. 1-4, 20.09.2011, p. 231-239.

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

BibTeX

@article{cedd35c9a62541dfb24fc8299f331fb4,

title = "State complexity of union and intersection for two-way nondeterministic finite automata",

abstract = "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.",

keywords = "Finite automata, partitions into sums of primes, state complexity, two-way automata",

author = "Michal Kunc and Alexander Okhotin",

year = "2011",

month = sep,

day = "20",

doi = "10.3233/FI-2011-540",

language = "English",

volume = "110",

pages = "231--239",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "1-4",

}

RIS

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 -

ID: 41140828