2011
Describing periodicity in two-way deterministic finite automata using transformation semigroups
KUNC, Michal a Alexander OKHOTINZá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
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
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
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 9. 12. 2011 16:02, doc. Mgr. Michal Kunc, Ph.D.
V originále
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.
Č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 VaV |
| ||
| MSM0021622409, záměr |
|