On uniform decision problems and abstract properties of small overlap monoids.

DOI10.1142/S0218196711006145zbMATH Open1237.20054arXiv0910.4857OpenAlexW2963610611MaRDI QIDQ2996845FDOQ2996845

Authors: Mark Kambites 

Publication date: 3 May 2011

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

Abstract: We study the way in which the abstract structure of a small overlap monoid is reflected in, and may be algorithmically deduced from, a small overlap presentation. We show that every C(2) monoid admits an essentially canonical C(2) presentation; by counting canonical presentations we obtain asymptotic estimates for the number of non-isomorphic monoids admitting a-generator, k-relation presentations of a given length. We demonstrate an algorithm to transform an arbitrary presentation for a C(m) monoid (m at least 2) into a canonical C(m) presentation, and a solution to the isomorphism problem for C(2) presentations. We also find a simple combinatorial condition on a C(4) presentation which is necessary and sufficient for the monoid presented to be left cancellative. We apply this to obtain algorithms to decide if a given C(4) monoid is left cancellative, right cancellative or cancellative, and to show that cancellativity properties are asymptotically visible in the sense of generic-case complexity.

Full work available at URL: https://arxiv.org/abs/0910.4857

Recommendations

• Small overlap monoids. I: The word problem.
• An explicit algorithm for normal forms in small overlap monoids
• Small overlap monoids. II: Automatic structures and normal forms.
• On two problems related to cancellativity
• Generic complexity of finitely presented monoids and semigroups

zbMATH Keywords

isomorphism problemword problemmonoid presentationscancellative monoidssmall overlap monoids

Mathematics Subject Classification ID

Cancellation theory of groups; application of van Kampen diagrams (20F06) Free semigroups, generators and relations, word problems (20M05)

Cites Work

• ALMOST EVERY GROUP IS HYPERBOLIC
• Word hyperbolic semigroups
• On the geometry of semigroup presentations
• 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 invariance of small overlap hypotheses

Cited In (6)

• Generic complexity of finitely presented monoids and semigroups
• Small overlap monoids. I: The word problem.
• Small overlap monoids. II: Automatic structures and normal forms.
• A cancellativity criterion for presented monoids
• 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: On uniform decision problems and abstract properties of small overlap monoids.

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