Generic complexity of finitely presented monoids and semigroups
From MaRDI portal
Publication:451108
DOI10.1007/s00037-011-0005-5zbMath1252.68153OpenAlexW1999298839MaRDI QIDQ451108
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
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