On the Connectivity of the Product of Automata

Article type: Research Article

Authors: Bavel, Zamir | Grzymała-Busse, Jerzy | Soo Hong, Kwang

Affiliations: University of Kansas

Abstract: Our main results include: Sufficient conditions for two strongly connected automata to have a strongly connected product. Sufficient conditions for the product of two connected automata to be connected and sufficient conditions for it to be not connected. Necessary and sufficient conditions for the product of two strongly connected automata, one of which is total, to be strongly connected. Necessary and sufficient conditions that a singly-generated subautomaton of the product be strongly connected. Necessary and sufficient conditions for the existence of an isomorphic copy of an automaton in its product with another.

Keywords: connected and strongly connected automata, directed product of automata, homomorphisms of automata

DOI: 10.3233/FI-1984-7204

Journal: Fundamenta Informaticae, vol. 7, no. 2, pp. 225-266, 1984