On properties not inherited by monoids from their Schützenberger groups.

DOI10.1016/J.IC.2011.03.004zbMATH Open1279.20069arXiv1012.2049OpenAlexW2050243749MaRDI QIDQ549674FDOQ549674

Authors: R. Gray, A. Malheiro, Stephen J. Pride 

Publication date: 18 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Abstract: We give an example of a monoid with finitely many left and right ideals, all of whose Schutzenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids M and N with isometric Cayley graphs, where N has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but M does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasi-isometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions.

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

Recommendations

• Homotopy bases and finite derivation type for Schützenberger groups of monoids.
• On finite presentability of monoids and their Schützenberger groups
• scientific article; zbMATH DE number 5218144
• FOR REWRITING SYSTEMS THE TOPOLOGICAL FINITENESS CONDITIONS FDT AND FHT ARE NOT EQUIVALENT
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)

zbMATH Keywords

finitely presented groupsfinite derivation typefinitely presented monoidshomotopy basescomplete rewriting systemsSchützenberger groups

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Grammars and rewriting systems (68Q42) 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)

Cites Work

• String rewriting for double coset systems.
• Structure of regular semigroups. I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Banach algebras on semigroups and on their compactifications
• Title not available (Why is that?)
• On the structure of semigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(\mathfrak q\)-theory of finite semigroups.
• Finiteness and CAT(0) properties of diagram groups.
• Diagram groups
• On subgroups of R. Thompson's group $ F$ and other diagram groups
• Diagram groups and directed 2-complexes: homotopy and homology.
• Amenability for discrete convolution semigroup algebras.
• Structure Results for Transitive, Untwisted, Superlinked Finite Covers
• Relative Ideals in Semigroups. II
• Green index and finiteness conditions for semigroups.
• On maximal subgroups of free idempotent generated semigroups.
• Subgroups of free idempotent generated semigroups need not be free.
• Metrics on diagram groups and uniform embeddings in a Hilbert space.
• Presentations for subgroups of monoids
• On residual finiteness of monoids, their Schützenberger groups and associated actions.
• Title not available (Why is that?)
• Rewriting systems in alternating knot groups with the Dehn presentation
• Finitely approximable regular semigroups
• Finite complete rewriting systems and finite derivation type for small extensions of monoids
• Rewriting systems and geometric three-manifolds
• A finiteness condition for rewriting systems
• Finiteness conditions on groups and quasi-isometries
• Finite homotopy bases of one-relator monoids
• On finite presentability of monoids and their Schützenberger groups
• Homotopy bases and finite derivation type for Schützenberger groups of monoids.
• Homological Finite Derivation Type
• Homotopy bases and finite derivation type for subgroups of monoids.
• Soluble groups with a finite rewriting system
• ON HOMOTOPICAL AND HOMOLOGICAL FINITENESS CONDITIONS FOR FINITELY PRESENTED MONOIDS
• For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
• Title not available (Why is that?)
• For finitely presented monoids the homological finiteness conditions FHT and \(\text{bi-FP}_3\) coincide
• String rewriting and homology of monoids
• Homological and finiteness properties of picture groups
• The word problem for free partially commutative groups
• Complete involutive rewriting systems
• Title not available (Why is that?)
• Coset Enumeration in a Finitely Presented Semigroup
• DETERMINING IDEALS OF A GIVEN FINITE INDEX IN A FINITELY PRESENTED SEMIGROUP
• Groups acting on semimetric spaces and quasi-isometries of monoids.
• The homological finiteness properties left-, right-, and bi-\(\mathbf{FP}_n\) of monoids.
• Finite complete rewriting systems for regular semigroups.

Cited In (4)

• Non-finitely generated maximal subgroups of context-free monoids
• Finite complete rewriting systems for regular semigroups.
• FOR REWRITING SYSTEMS THE TOPOLOGICAL FINITENESS CONDITIONS FDT AND FHT ARE NOT EQUIVALENT
• On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids

Uses Software

• kan

This page was built for publication: On properties not inherited by monoids from their Schützenberger groups.

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