Michal Kunc and Alexander Okhotin

**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_{0 ≤ ℓ ≤ n} *G*(*n* − *ℓ*) + *ℓ* + 1 states, where *G*(*k*) is the maximum order of a permutation of *k* elements.