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

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal OKHOTIN Alexander

Year of publication 2011
Type Article in Periodical
Magazine / Source Fundamenta Informaticae
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.3233/FI-2011-540
Field General mathematics
Keywords finite automata; two-way automata; state complexity; partitions into sums of primes
Description 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 not equal to 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 not in {4,6} (with a few more exceptions) into sums of pairwise distinct primes is established as well.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.