Inverse monoids, trees, and context-free languages. (English) Zbl 0795.20043

This paper concerns a research direction connected with the use of algebraic methods in the theories of automata, formal languages and grammars. Main attention is paid to universe semigroups and monoids [M. Petrich, Inverse semigroups, Wiley (1984; Zbl 0546.20053)].
An inverse semigroup is a semigroup \(S\) with the property that for each \(a\in S\) there is a unique element \(a^{-1}\in S\) such that \(a= aa^{- 1} a\) and \(a^{-1}= a^{-1} aa^{-1}\). If \(S\) has an identity 1, we refer to it as inverse monoid. Relations of order, congruence, factor-set and isomorphic and homomorphic constructions based on that notions are introduced.
In the finitely presented case the word problem is solved by using Rabin’s theorem on the second order monadic logic of the infinite binary tree [M. O. Rabin, Trans. Am. Math. Soc. 141, 1-35 (1969; Zbl 0221.02031)]. Some connections with the theory of rational subsets of the free group and the theory of context-free languages are explored.


20M05 Free semigroups, generators and relations, word problems
20M18 Inverse semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
Full Text: DOI