Trees associated to inverse monoid presentations (Q5956884)

Schützenberger graphs play in inverse monoid theory a role similar to the one played by Cayley graphs in group theory. The problem of characterizing those graphs which appear as Schützenberger graphs of inverse monoids can be traced back to a paper by \textit{S. W. Margolis} and \textit{J. C. Meakin} [Semigroup Forum 44, No. 2, 137-148 (1992; Zbl 0757.20017)], where they introduced a necessary and sufficient condition for a tree to be a Schützenberger graph for some idempotent-pure inverse monoid presentation and they proposed the problem of determining necessary and sufficient conditions for a (rational) tree to be a Schützenberger graph for some finite idempotent-pure inverse monoid presentation.NEWLINENEWLINENEWLINEThe main aim of the author in this paper is to establish a necessary and sufficient condition for a tree to be a Schützenberger graph for some finite inverse monoid presentation, and to show that this condition is decidable for an arbitrary rational tree. The author also proves that the condition introduced by Margolis and Meakin for arbitrary inverse monoid presentations (existence of a finite test tree) is decidable for rational trees.