KUNC, Michal a Alexander OKHOTIN. Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Giancarlo Mauri, Alberto Leporati. Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. Berlin: Springer, 2011, s. 324-336. ISBN 978-3-642-22320-4. Dostupné z: https://dx.doi.org/10.1007/978-3-642-22321-1_28.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název 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 (203 Česká republika, garant, domácí) a Alexander OKHOTIN (643 Rusko).
Vydání Berlin, Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, od s. 324-336, 13 s. 2011.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10101 Pure mathematics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14310/11:00050221
Organizační jednotka Přírodovědecká fakulta
ISBN 978-3-642-22320-4
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-22321-1_28
Klíčová slova česky konečné automaty; dvoucestné deterministické automaty; periodicita; transformační pologrupy; unární jazyky
Klíčová slova anglicky finite automata; two-way deterministic automata; periodicity; transformation semigroups; unary languages
Štítky AKR, rivok
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. Mgr. Michal Kunc, Ph.D., učo 2906. Změněno: 9. 12. 2011 16:02.
Anotace
A framework for the study of periodic behaviour of two-way deterministic finite automata (2DFA) is developed. Computations of 2DFAs are represented by a two-way analogue of transformation semigroups, every element of which describes the behaviour of a 2DFA on a certain string x. A subsemigroup generated by this element represents the behaviour on strings in x^+. The main contribution of this paper is a description of all such monogenic subsemigroups up to isomorphism. This characterization is then used to show that transforming an n-state 2DFA over a one-letter alphabet to an equivalent sweeping 2DFA requires exactly n + 1 states, and transforming it to a one-way automaton requires exactly max{G(n-l) + l + 1 | 0 <= l <= n} states, where G(k) is the maximum order of a permutation of k elements.
Anotace česky
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ů.
Návaznosti
GA201/09/1313, projekt VaVNázev: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II
MSM0021622409, záměrNázev: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace
VytisknoutZobrazeno: 20. 5. 2024 00:13