Applications of automata theory to presentations of monoids and inverse monoids
Joseph B. Stephen · Lincoln (University of Nebraska) · 1987
There is a strong connection between monoids, automata and languages. The traditional approach is to exploit properties of the syntactic monoid of an automaton to derive characteristics of the language recognized by the automaton. In this work we construct certain automata and exploit the characteristics of these automata to derive information about monoids. A monoid is a semigroup with an identity (which we will always denote by 1). We consider the word problem for monoids $M\ =\ Mon\langle A\vert S\rangle$ and inverse monoids $N\ =\ Inv\langle X\vert R\rangle$. In this work we establish the importance and effectiveness of graphical methods in approaching the word problem in monoids and inverse monoids. We show that: (a) Given a presentation of a monoid $M = Mon\langle A\vert S\rangle$, there is a unique birooted word graph over $A$ associated with each $m \in M$. (b) Given a presentation of an inverse monoid $N = Inv\langle X\vert R\rangle$, there is a unique birooted inverse word graph over $X$ associated with each $n \in N$. We give constructive techniques to determine approximates of these graphs with respect to presentations of monoids and inverse monoids. We describe and exploit the properties of the geometry of these birooted word graphs and their languages. We prove the decidability of a class of monoid presentations and a large class of previously unsolved word problems for inverse monoid presentations. This work establishes the first coherent framework for studying the word problem for presentations of inverse monoids.