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

DOI10.1142/S0218196711006145MaRDI QIDQ2996845zbMATH OpenOpenAlexFDO

Authors Mark Kambites

Publication date 3 May 2011

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

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

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)

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.

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

Cites work

• ALMOST EVERY GROUP IS HYPERBOLIC
• Easy multiplications. I: The realm of Kleene's theorem
• On the geometry of semigroup presentations
• On the invariance of small overlap hypotheses
• Small overlap monoids. I: The word problem.
• Small overlap monoids. II: Automatic structures and normal forms.
• Word hyperbolic semigroups

Cited in

(6)

• A note on the definition of small overlap monoids.
• An explicit algorithm for normal forms in small overlap monoids
• A cancellativity criterion for presented monoids
• Small overlap monoids. I: The word problem.
• Small overlap monoids. II: Automatic structures and normal forms.
• Generic complexity of finitely presented monoids and semigroups

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)