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 | |
| Rok publikování | 2011 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Fundamenta Informaticae |
| Fakulta / Pracoviště MU | |
| 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: |