2011
State complexity of union and intersection for two-way nondeterministic finite automata
KUNC, Michal and Alexander OKHOTINBasic information
Original name
State complexity of union and intersection for two-way nondeterministic finite automata
Name in Czech
Stavová složitost sjednocení a průniku pro dvoucestné nedeterministické konečné automaty
Authors
KUNC, Michal (203 Czech Republic, guarantor, belonging to the institution) and Alexander OKHOTIN (643 Russian Federation)
Edition
Fundamenta Informaticae, Amsterdam, IOS Press, 2011, 0169-2968
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10101 Pure mathematics
Country of publisher
Netherlands
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 0.365
RIV identification code
RIV/00216224:14310/11:00050220
Organization unit
Faculty of Science
UT WoS
000294764900018
Keywords (in Czech)
konečné automaty; dvoucestné automaty; stavová složitost; rozklady na součty prvočísel
Keywords in English
finite automata; two-way automata; state complexity; partitions into sums of primes
Tags
International impact, Reviewed
Changed: 9/12/2011 17:11, doc. Mgr. Michal Kunc, Ph.D.
V originále
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.
In Czech
V článku je dokázáno, že počet stavů v dvoucestném nedeterministickém konečném automatu (2NFA) potřebných k reprezentování průniku jazyků daných 2NFA s m stavy a 2NFA s n stavy je alespoň m + n a nejvýše m + n + 1. Pro operaci sjednocení je počet stavů přesně m + n. Dolní mez je stanovena pro jazyky nad abecedou s jedním písmenem. Klíčový argument je založen na následujícím lemmatu: pro všechna m,n >= 2 různá od 6 (a s konečně mnoha dalšími výjimkami) existují rozklady m = p1 +...+ pk a n = q1 +...+ ql, kde všechna čísla p1,...,pk,q1,...,ql >= 2 jsou mocninami po dvou různých prvočísel. Pro úplnost je dokázáno rovněž analogické tvrzení o rozkladech libovolných dvou čísel m,n nepatřících do {4,6} (s několika dalšími výjimkami) na součty po dvou různých prvočísel.
Links
| GA201/09/1313, research and development project |
|