The loop problem for monoids and semigroups

DOI10.1017/S0305004107000606MaRDI QIDQ5428377zbMATH OpenOpenAlexFDO

Authors Mark Kambites

Publication date 22 November 2007

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

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

zbMATH Keywords

automataCayley graphscontext-free languagesloop problemword problem

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: We propose a way of associating to each finitely generated monoid or semigroup a formal language, called its loop problem. In the case of a group, the loop problem is essentially the same as the word problem in the sense of combinatorial group theory. Like the word problem for groups, the loop problem is regular if and only if the monoid is finite. We study also the case in which the loop problem is context-free, showing that a celebrated group-theoretic result of Muller and Schupp extends to describe completely simple semigroups with context-free loop problems. We consider also right cancellative monoids, establishing connections between the loop problem and the structural theory of these semigroups by showing that the syntactic monoid of the loop problem is the inverse hull of the monoid.

Recommendations

• The loop problem for Rees matrix semigroups.
• GROUPS AND SEMIGROUPS WITH A ONE-COUNTER WORD PROBLEM
• Semigroups with a Context-Free Word Problem
• Word problem languages for free inverse monoids
• On the word problem for free products of semigroups and monoids

Cites work

• Automatic semigroups
• Groups, the theory of ends, and context-free languages
• On the definition of word hyperbolic groups.
• On the Group of a Set of Partial Transformations
• On torsion-free groups with infinitely many ends
• Subgroups of finitely presented groups
• The accessibility of finitely presented groups
• Word hyperbolic semigroups

Cited in

(4)

• The loop problem for Rees matrix semigroups.
• Inverse monoids: decidability and complexity of algebraic questions.
• The next step of the word problem over monoids.
• Homological finiteness properties of monoids, their ideals and maximal subgroups.

This page was built for publication: The loop problem for monoids and semigroups

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