Digraphs, automata and sandwich semigroups of binary relations

Abstract

This work is an outgrowth of recent work done investigating the transfer of information between automata and various semigroups associated with automata. Dennis Geller has introduced some relationships concerning automata and studied the information semigroups of automata give about these relationships and vice-versa. Also, A. C. Fleck, E. T. Hedetniemi and R. H. Oehmke have introduced graph isomorphism between automata and studied S-semigroups of automata. We generalize the concept of S-semigroups and study these new semigroups in terms of pathwise isomorphism. We show that our semigroups are isomorphic in a certain sense if and only if their respective machines are pathwise isomorphic. We also show that the usual machine isomorphism implies pathwise isomorphism, but not conversely. Since diagraphs can be associated with automata, some of our work applies to digraphs. Our new semigroups associated with automata lead us naturally to new semigroups of binary relations. In particular we introduce a new multiplication on binary relations by means of an arbitrary but fixed "sandwich" relation. We give algorithms for constructing idempotents and regular elements in these new semigroups. R. J. Plemmons and M. West have characterized Green's relations in the usual semigroup of binary relations, and we use these to characterize Green's relations in our semigroups.