Inverse monoids: decidability and complexity of algebraic questions. (Q2643082)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Inverse monoids: decidability and complexity of algebraic questions. |
scientific article; zbMATH DE number 5182189
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Inverse monoids: decidability and complexity of algebraic questions. |
scientific article; zbMATH DE number 5182189 |
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
0.9846084117889404
0 references
0.8594915866851807
0 references
0.8545998930931091
0 references
0.838679850101471
0 references
0.8381208181381226
0 references
