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

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal OKHOTIN Alexander

Year of publication 2011
Type Article in Proceedings
Conference Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1007/978-3-642-22321-1_28
Field General mathematics
Keywords finite automata; two-way deterministic automata; periodicity; transformation semigroups; unary languages
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.