Chains of Finite Automat a with Bounded Number of Chains 1

Abstract

Chains of finite automata are considered. We show that if the lowest automaton in a chain controls movements of the common reading head then computing power of the chain is very limited. This is a generalization of Krohn-Rhodes theorem on one-way automata.