Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
type: Item
instance of: scholarly article
title: Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
zbMATH Open document ID: 1172.20041
author: Emanuele Rodaro
author: A. Cherubini
published in: Semigroup Forum
publication date: 2008-12-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M18
Mathematics Subject Classification ID: 20E06
zbMATH DE Number: 5377126
zbMATH Keywords: finite inverse semigroups
zbMATH Keywords: word problem
zbMATH Keywords: Schützenberger automata
zbMATH Keywords: Yamamura HNN-exstensions
MaRDI profile type: Publication
full work available at URL: s00233-008-9050-z
OpenAlex ID: W2057275313
cites work: Amalgamated free products of inverse semigroups
cites work: Amalgams of finite inverse semigroups.
cites work: HNN extensions of inverse semigroups and groupoids.
cites work: Embedding Theorems for Groups
cites work: EMBEDDING THEOREMS FOR SEMIGROUPS
cites work: The Word Problem for HNN-extensions of Free Inverse Semigroups
cites work: Q4537454
cites work: Q4145882
cites work: Groupoids, inverse semigroups, and their operator algebras
cites work: Q3337662
cites work: Amalgams vs Yamamura's HNN-Extensions of Inverse Semigroups
cites work: Algorithmic problems for amalgams of finite semigroups
cites work: Presentations of inverse monoids
cites work: HNN Extensions of Inverse Semigroups and Applications
DOI: 10.1007/S00233-008-9050-Z
description: scientific article; zbMATH DE number 5377126