Generic complexity of finitely presented monoids and semigroups

DOI10.1007/S00037-011-0005-5MaRDI QIDQ451108zbMATHOpenAlexFDO

Authors Mark Kambites

Publication date 21 September 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-011-0005-5

zbMATH Keywords

semigroupsmonoidsfinite presentationsgeneric-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05)

Recommendations

• Small overlap monoids. I: The word problem.
• On uniform decision problems and abstract properties of small overlap monoids.
• scientific article; zbMATH DE number 4071227
• Generic-case complexity, decision problems in group theory, and random walks.
• An explicit algorithm for normal forms in small overlap monoids

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 52907 (Why is no real title available?)
• scientific article; zbMATH DE number 176768 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3045417 (Why is no real title available?)
• ALMOST EVERY GROUP IS HYPERBOLIC
• Combinatorial group theory and public key cryptography
• Easy multiplications. I: The realm of Kleene's theorem
• Generic-case complexity, decision problems in group theory, and random walks.
• Length-based cryptanalysis: the case of Thompson's group
• On the geometry of semigroup presentations
• Recursive unsolvability of a problem of Thue
• Small overlap monoids. I: The word problem.
• Small overlap monoids. II: Automatic structures and normal forms.
• Thompson’s Group and Public Key Cryptography
• Word hyperbolic semigroups

Cited in

(11)

• Generic complexity of the word problem in some semigroups
• scientific article; zbMATH DE number 7444014 (Why is no real title available?)
• A note on the definition of small overlap monoids.
• Infinitely generated semigroups and polynomial complexity
• An explicit algorithm for normal forms in small overlap monoids
• scientific article; zbMATH DE number 4216027 (Why is no real title available?)
• On uniform decision problems and abstract properties of small overlap monoids.
• The word problem for one-relation monoids: a survey
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• Complexity results on the conjugacy problem for monoids
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET

This page was built for publication: Generic complexity of finitely presented monoids and semigroups

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