Generic complexity of finitely presented monoids and semigroups
From MaRDI portal
Publication:451108
DOI10.1007/S00037-011-0005-5zbMATH Open1252.68153OpenAlexW1999298839MaRDI QIDQ451108FDOQ451108
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
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
Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Thompson’s Group and Public Key Cryptography
- Title not available (Why is that?)
- ALMOST EVERY GROUP IS HYPERBOLIC
- Length-based cryptanalysis: the case of Thompson's group
- Recursive unsolvability of a problem of Thue
- Word hyperbolic semigroups
- Combinatorial group theory and public key cryptography
- On the geometry of semigroup presentations
- Generic-case complexity, decision problems in group theory, and random walks.
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
Cited In (11)
- THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
- Generic complexity of the word problem in some semigroups
- Title not available (Why is that?)
- On uniform decision problems and abstract properties of small overlap monoids.
- Title not available (Why is that?)
- STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
- The word problem for one-relation monoids: a survey
- Complexity results on the conjugacy problem for monoids
- Infinitely generated semigroups and polynomial complexity
- An explicit algorithm for normal forms in small overlap monoids
- A note on the definition of small overlap monoids.
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)
