Small overlap monoids. I: The word problem.

DOI10.1016/J.JALGEBRA.2008.09.038MaRDI QIDQ1024387zbMATHOpenAlexFDO

Authors Mark Kambites

Publication date 17 June 2009

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

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

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)

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.

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.

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 52907 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• ALMOST EVERY GROUP IS HYPERBOLIC
• Combinatorial group theory and public key cryptography
• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups
• On the geometry of semigroup presentations

Cited in

(9)

• The next step of the word problem over monoids.
• How effects efficiency on the word problem for monoids?
• A note on the definition of small overlap monoids.
• An explicit algorithm for normal forms in small overlap monoids
• Word problem of the Perkins semigroup via directed acyclic graphs.
• On uniform decision problems and abstract properties of small overlap monoids.
• Small overlap monoids. II: Automatic structures and normal forms.
• The word problem for one-relation monoids: a survey
• Generic complexity of finitely presented monoids and semigroups

Describes a project that uses

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)