Inverse monoids: decidability and complexity of algebraic questions. (Q2643082)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Inverse monoids: decidability and complexity of algebraic questions. |
scientific article |
Statements
Inverse monoids: decidability and complexity of algebraic questions. (English)
0 references
23 August 2007
0 references
The authors show that the word problem can be solved in linear time on a RAM and in logarithmic space for the class of inverse monoids generated by a set \(\Gamma\) subject to relations of the form \(e=f\), where \(e\) and \(f\) are idempotents in the free inverse monoid generated by \(\Gamma\). Also, it is shown that the first-order theory with regular path predicates is decidable for the Cayley-graphs of these monoids.
0 references
inverse monoids
0 references
word problem
0 references
Cayley graphs
0 references
algorithmic complexity
0 references
first-order theories
0 references
0 references
