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

KUNC, Michal and 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, p. 324-336. ISBN 978-3-642-22320-4. Available from: https://dx.doi.org/10.1007/978-3-642-22321-1_28.

Basic 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

• Original 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: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-642-22321-1_28
• 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: AKR, rivok
• Tags: International impact, Reviewed

Abstract

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.

Abstract (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: Name: Algebraické metody v teorii automatů a formálních jazyků II

Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory II

• MSM0021622409, plan (intention): Name: Matematické struktury a jejich fyzikální aplikace

Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures and their physical applications