A survey on the computational power of some classes of finite monoid presentations (Q4942274)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1419255
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A survey on the computational power of some classes of finite monoid presentations |
scientific article; zbMATH DE number 1419255 |
Statements
9 October 2000
0 references
decision problems
0 references
word problems
0 references
finitely presented monoids
0 references
decidability
0 references
undecidability
0 references
finite presentations
0 references
0.8353850245475769
0 references
0.8295877575874329
0 references
0.7996828556060791
0 references
0.7912144660949707
0 references
A survey on the computational power of some classes of finite monoid presentations (English)
0 references
The author surveys recent results on various decision problems, including the word problem, for finitely presented monoids. Though many algebraic properties are undecidable for finite presentations in general, some properties become decidable for suitable restricted classes of presentations. The paper gives both decidability and undecidability results for finite presentations which are convergent, \(\lambda\)-confluent, monadic or/and special. The author also reports on a software system which implements the algorithmic solutions for the decision problems discussed in the paper. For the entire collection see [Zbl 0931.00032].
0 references