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

M Kunc, A Okhotin - … Conference on Developments in Language Theory, 2011 - Springer
M Kunc, A Okhotin
International Conference on Developments in Language Theory, 2011Springer
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 …
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 states, where G(k) is the maximum order of a permutation of k elements.
Springer