Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups. (Q958188): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 19:51, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups. |
scientific article |
Statements
Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups. (English)
0 references
2 December 2008
0 references
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.
0 references
finite inverse semigroups
0 references
word problem
0 references
Schützenberger automata
0 references
Yamamura HNN-exstensions
0 references