Describing periodicity in two-way deterministic finite automata using transformation semigroups

Název česky Popis periodicity v dvoucestných deterministických konečných automatech pomocí transformačních pologrup
Autoři

KUNC Michal OKHOTIN Alexander

Druh Článek ve sborníku
Konference Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1007/978-3-642-22321-1_28
Obor Obecná matematika
Klíčová slova finite automata; two-way deterministic automata; periodicity; transformation semigroups; unary languages
Popis V tomto článku je vyvinuta technika pro studium periodického chování dvoucestných deterministických konečných automatů (2DFA). Výpočty 2DFA jsou reprezentovány dvoucestnou analogií transformačních pologrup, jejichž každý prvek popisuje chování 2DFA na určitém řetězci x. Podpologrupa generovaná tímto prvkem reprezentuje chování na řetězcích v x^+. Hlavním příspěvkem článku je popis všech takových monogenických podpologrup až na izomorfismus. Pomocí této charakterizace je poté ukázáno, že k transformování 2DFA s n stavy nad jednopísmennou abecedou na ekvivalentní zametací 2DFA je třeba právě n + 1 stavů a k jeho transformování na jednocestný automat je třeba právě max{G(n-l) + l + 1 | 0 <= l <= n} stavů, kde G(k) je největší řád permutace k prvků.
Související projekty:

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