2011
Describing periodicity in two-way deterministic finite automata using transformation semigroups
KUNC, Michal and Alexander OKHOTINBasic information
Original name
Describing periodicity in two-way deterministic finite automata using transformation semigroups
Name in Czech
Popis periodicity v dvoucestných deterministických konečných automatech pomocí transformačních pologrup
Authors
KUNC, Michal (203 Czech Republic, guarantor, belonging to the institution) and Alexander OKHOTIN (643 Russian Federation)
Edition
Berlin, Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, p. 324-336, 13 pp. 2011
Publisher
Springer
Other information
Language
English
Type of outcome
Proceedings paper
Field of Study
10101 Pure mathematics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14310/11:00050221
Organization unit
Faculty of Science
ISBN
978-3-642-22320-4
ISSN
Keywords (in Czech)
konečné automaty; dvoucestné deterministické automaty; periodicita; transformační pologrupy; unární jazyky
Keywords in English
finite automata; two-way deterministic automata; periodicity; transformation semigroups; unary languages
Tags
International impact, Reviewed
Changed: 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.
In Czech
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ů.
Links
| GA201/09/1313, research and development project |
| ||
| MSM0021622409, plan (intention) |
|