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
• Rok publikování: 2011
• 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
• 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

• Matematické struktury a jejich fyzikální aplikace
• Algebraické metody v teorii automatů a formálních jazyků II