Amalgams of finite inverse semigroups and deterministic context-free languages. (Q1758227): Difference between revisions

The paper deals with the standard presentation \(\langle X\mid R\rangle\) of an amalgam \(S=[S_1,S_2;U]\) of finite inverse semigroups. Through the investigation of the structure of the Schützenberger graph \(S\Gamma(X,R;w)\) of a representative \(w\in(X\cup X^{-1})^+\) of an element \(s\) of~\(S\), several algorithmic conclusions are drawn. The main ingredient is to show that \(S\Gamma(X,R;w)\) is a context-free graph in the sense of \textit{D. E. Müller} and \textit{P. E. Schupp} [Bull. Am. Math. Soc., New Ser. 4, 331-334 (1981; Zbl 0484.03019)], and whence the transition graph of a pushdown automaton. Thus, the language recognized by the associated Schützenberger automaton, which recognizes the language of all representatives of elements of \(S\) which lie above \(s\) in the natural order, is a context-free language. An explicit construction for a pushdown automaton recognizing this language is also given. As an application, the authors show that the non-uniform word problem for amalgams of finite inverse semigroups is solvable in polynomial time; decidability had previously been established by \textit{A. Cherubini, J. Meakin} and \textit{B. Piochi} [J. Algebra 285, No. 2, 706-725 (2005; Zbl 1069.20052)]. Another application is that it is decidable whether all \(\mathcal D\)-classes in such an amalgam are finite.