Small overlap monoids. II: Automatic structures and normal forms.

DOI10.1016/J.JALGEBRA.2008.12.028MaRDI QIDQ1024392zbMATH OpenOpenAlexFDO

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/0806.3891

zbMATH Keywords

automatic structuresfinite presentationsKleene theoremsnormal form theoremsrational monoidsrational subsetssemigroupssmall cancellation theorysmall overlap conditionssmall overlap monoidsword problem

Mathematics Subject Classification ID

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) Formal languages and automata (68Q45)

Abstract: We show that any finite monoid or semigroup presentation satisfying the small overlap condition C(4) has word problem which is a deterministic rational relation. It follows that the set of lexicographically minimal words forms a regular language of normal forms, and that these normal forms can be computed in linear time. We also deduce that C(4) monoids and semigroups are rational (in the sense of Sakarovitch), asynchronous automatic, and word hyperbolic (in the sense of Duncan and Gilman). From this it follows that C(4) monoids satisfy analogues of Kleene's theorem, and admit decision algorithms for the rational subset and finitely generated submonoid membership problems. We also prove some automata-theoretic results which may be of independent interest.

Recommendations

• Small overlap monoids. I: The word problem.
• An explicit algorithm for normal forms in small overlap monoids
• On uniform decision problems and abstract properties of small overlap monoids.
• MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS
• A note on the definition of small overlap monoids.

Cites work

• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 3911744 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (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 1944128 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Multitape one-way nonwriting automata
• On Relations Defined by Generalized Finite Automata
• On the definition of word hyperbolic groups.
• On the geometry of semigroup presentations
• On the rational subset problem for groups.
• Rational equivalence relations
• Word hyperbolic semigroups

Cited in

(9)

• Small overlap monoids. I: The word problem.
• The word problem for one-relation monoids: a survey
• A finiteness criterion for inverse semigroups
• A note on the definition of small overlap monoids.
• On uniform decision problems and abstract properties of small overlap monoids.
• Generic complexity of finitely presented monoids and semigroups
• scientific article; zbMATH DE number 4116825 (Why is no real title available?)
• An explicit algorithm for normal forms in small overlap monoids
• Membership problems for positive one-relator groups and one-relation monoids

This page was built for publication: Small overlap monoids. II: Automatic structures and normal forms.

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