Small overlap monoids. I: The word problem.

DOI10.1016/J.JALGEBRA.2008.09.038zbMATH Open1222.20039arXiv0712.0250OpenAlexW2963463670MaRDI QIDQ1024387FDOQ1024387

Mark Kambites

Publication date: 17 June 2009

Published in: Journal of Algebra (Search for Journal in Brave)

Abstract: We develop a combinatorial approach to the study of semigroups and monoids with finite presentations satisfying small overlap conditions. In contrast to existing geometric methods, our approach facilitates a sequential left-right analysis of words which lends itself to the development of practical, efficient computational algorithms. In particular, we obtain a highly practical linear time solution to the word problem for monoids and semigroups with finite presentations satisfying the condition C(4), and a polynomial time solution to the uniform word problem for presentations satisfying the same condition.

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

Recommendations

• An explicit algorithm for normal forms in small overlap monoids
• Small overlap monoids. II: Automatic structures and normal forms.
• On uniform decision problems and abstract properties of small overlap monoids.
• On the invariance of small overlap hypotheses
• A note on the definition of small overlap monoids.

zbMATH Keywords

semigroupssmall cancellation theoryword problemmonoidsfinite presentationssmall overlap conditions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cancellation theory of groups; application of van Kampen diagrams (20F06) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• ALMOST EVERY GROUP IS HYPERBOLIC
• Title not available (Why is that?)
• Combinatorial group theory and public key cryptography
• On the geometry of semigroup presentations
• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups

Cited In (8)

• Generic complexity of finitely presented monoids and semigroups
• Small overlap monoids. II: Automatic structures and normal forms.
• Word problem of the Perkins semigroup via directed acyclic graphs.
• The word problem for one-relation monoids: a survey
• ON UNIFORM DECISION PROBLEMS AND ABSTRACT PROPERTIES OF SMALL OVERLAP MONOIDS
• The next step of the word problem over monoids.
• An explicit algorithm for normal forms in small overlap monoids
• A note on the definition of small overlap monoids.

Uses Software

• GAP
• Smalloverlap

This page was built for publication: Small overlap monoids. I: The word problem.

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