Generic complexity of finitely presented monoids and semigroups

DOI10.1007/s00037-011-0005-5zbMath1252.68153OpenAlexW1999298839MaRDI QIDQ451108

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)

Related Items

An explicit algorithm for normal forms in small overlap monoids, A note on the definition of small overlap monoids., The word problem for one-relation monoids: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small overlap monoids. I: The word problem.
• Small overlap monoids. II: Automatic structures and normal forms.
• Easy multiplications. I: The realm of Kleene's theorem
• On the geometry of semigroup presentations
• Generic-case complexity, decision problems in group theory, and random walks.
• Combinatorial group theory and public key cryptography
• Thompson’s Group and Public Key Cryptography
• ALMOST EVERY GROUP IS HYPERBOLIC
• Word hyperbolic semigroups
• Recursive Unsolvability of a problem of Thue
• Length-based cryptanalysis: the case of Thompson's group