Chains of Finite Automat a with Bounded Number of Chains¹

Article type: Research Article

Authors: Kutylowski, Miroslaw^{; *}

Affiliations: Institute of Computer Science, University of Wroclaw, ul. Przesmyckiego 20, 51-151 Wroclaw, Poland

Note: [1] This research received support from Institute of Computer Science, University of Warsaw under program RP.I.09. Camera ready copy was prepared thanks to TH Darmstadt and Alexander von Humboldt Foundation.

Note: [*] Present address: Institut f. Theoretische Informatik, Technische Hochschule Darmstadt, Alexanderstr. 24, 6100 Darmstadt, West Germany.

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.

DOI: 10.3233/FI-1988-11304

Journal: Fundamenta Informaticae, vol. 11, no. 3, pp. 267-273, 1988