Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups. (Q958188): Difference between revisions

The authors consider a version of HNN extensions for inverse semigroups suggested by \textit{A. Yamamura} [Int. J. Algebra Comput. 7, No. 5, 605-624 (1997; Zbl 0892.20036)]. They prove that, for every finite inverse semigroup \(S\), the word problem in Yamamura's HNN extension \(S^*\) of \(S\) is decidable. Given two inverse semigroup words \(w_1,w_2\) over the canonical generating set of \(S^*\), the decision algorithm proceeds by an iterative construction of a sequence of finite automata approximating the Schützenberger automaton of \(w_1\) with respect to the canonical presentation of \(S^*\). The authors prove that it is possible to check whether or not the word \(w_2\) is accepted by the Schützenberger automaton by inspecting the first \(K\) automata in the sequence where the number \(K\) depends only on \(w_2\). The iterative construction of approximations to the Schützenberger automaton is similar to the one used by the second author, \textit{J. Meakin} and \textit{B. Piochi} [J. Algebra 285, No. 2, 706-725 (2005; Zbl 1069.20052)] to prove decidability of the word problem in amalgamated free products of finite inverse semigroups in the category of inverse semigroups.