DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS

DOI10.1142/S0218196709005366MaRDI QIDQ3643581zbMATH OpenOpenAlexFDO

Authors Alan J. Cain, Victor Maltcev

Publication date 9 November 2009

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218196709005366

zbMATH Keywords

decision problemsfinitely presented semigroupsMarkov propertiessemigroup presentationsundecidabilityundecidable problems

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10)

Recommendations

• scientific article; zbMATH DE number 1535398
• New undecidability results for finitely presented monoids
• scientific article; zbMATH DE number 3323852
• scientific article; zbMATH DE number 4071227
• Some undecidable embedding problems for finite semigroups

Cites work

• A complete rewrite system and normal forms for \((S)_{\text{reg}}\)
• Conjugacy in special monoids
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Generators and relations of direct products of semigroups
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• Left-divisibility and word problems in single relation monoids
• On monoids presented by a single relation
• On one-relator monoids and one-relator groups
• ON THE CONJUGACY PROBLEM FOR ONE-RELATOR MONOIDS WITH ELEMENTS OF FINITE ORDER
• On the geometry of semigroup presentations
• Recursive unsolvability of a problem of Thue
• SUBSEMIGROUPS OF THE BICYCLIC MONOID

Cited in

(9)

• A note on decidability questions on presentations of word semigroups
• Decidability and independence of conjugacy problems in finitely presented monoids
• Some decision problems concerning semilinearity and commutation.
• The word problem for one-relation monoids: a survey
• Finite semigroups embed in finitely presented congruence-free monoids.
• scientific article; zbMATH DE number 4071227 (Why is no real title available?)
• scientific article; zbMATH DE number 1512762 (Why is no real title available?)
• DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS
• The Todd-Coxeter algorithm for semigroups and monoids

This page was built for publication: DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3643581)