Pseudovarieties of inverse monoids
Robert Ruyle · Lincoln (University of Nebraska) · 1997
Recently, Margolis and Meakin showed that the set of all rooted inverse graphs (partial permutation graphs) over X is in one-to-one correspondence with the set of all closed inverse submonoids of the free inverse monoid FIM(X). In this dissertation we consider applications of inverse automata to the study of groups and inverse monoids. The first part of this work consists of a description of the lattice of all closed inverse submonoids of a free inverse monoid and a one-to-one correspondence with the lattice of all inverse automata. It is followed by results that provide an algorithm for calculating all Schutzenberger automata associated with a given finite inverse automaton. Next an Eilenberg type correspondence between pseudovarieties of inverse monoids and varieties of inverse automata is presented. The varieties of inverse automata we consider are naturally equivalent to varieties of recognizable closed inverse submonoids of a free inverse monoid and can be viewed as a refinement of the classical concept of varieties of recognizable languages. The problem of deciding whether a given system of equations and inequations has a solution in a given group has attracted considerable attention recently. We relate this problem to the setting of pseudovarieties of inverse monoids by introducing another view of inverse automata. An inverse automaton can be thought of as representing a system of equations and inequations in a group and, conversely, any finite system of equations and inequations can be associated with a finite inverse automaton. For certain groups G the problem of deciding whether a given system of equations and inequations has a solution in G is shown to be algorithmically equivalent to the problem of deciding membership in the variety of graphs generated by all finite subgraphs of all Cayley graphs of G. In particular, the membership problem for the variety generated by all finite trees is shown to be decidable as a result of Makanin's theorem concerning the decidability of solving systems of equations and inequations in a free group.