The word problem of inverse monoids presented by one idempotent relator (Q1314383)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The word problem of inverse monoids presented by one idempotent relator |
scientific article |
Statements
The word problem of inverse monoids presented by one idempotent relator (English)
0 references
27 March 1994
0 references
The paper studies inverse semigroups presented by a finite set of generators \(X \cup X^{-1}\) and one relation \(e = 1\), where \(e\) represents an idempotent in the free inverse monoid, and 1 is the empty word. The word problem for inverse monoids is generally undecidable, but here the automaton approach of Stephen is used to prove that the decidability problem for words \(u\), \(v\) has complexity bounded by a cubic polynomial on the sum of the lengths of \(u\), \(v\) and \(e\), (if \(e\) is positively labelled, meaning that every vertex of its Munn tree is in \(X^*\), the complexity of the problem is linear). Moreover, it is shown that the set of words in the congruence class (in the free monoid) of \(u\) is a deterministic context-free language.
0 references
inverse semigroups
0 references
generators
0 references
idempotent
0 references
free inverse monoid
0 references
word problem
0 references
automaton
0 references
complexity
0 references
Munn tree
0 references
deterministic context-free language
0 references