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

Název česky Stavová složitost sjednocení a průniku pro dvoucestné nedeterministické konečné automaty
Autoři

KUNC Michal OKHOTIN Alexander

Druh Článek v odborném periodiku
Časopis / Zdroj Fundamenta Informaticae
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.3233/FI-2011-540
Obor Obecná matematika
Klíčová slova finite automata; two-way automata; state complexity; partitions into sums of primes
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.