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

      0 references
      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
      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

      Identifiers