On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids

DOI10.1016/J.IC.2017.05.003zbMATH Open1371.68135arXiv1407.7428OpenAlexW2963762980MaRDI QIDQ2013556FDOQ2013556

Authors: Alan J. Cain, R. Gray, A. Malheiro 

Publication date: 8 August 2017

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

Abstract: This paper investigates the class of finitely presented monoids defined by homogeneous (length-preserving) relations from a computational perspective. The properties of admitting a finite complete rewriting system, having finite derivation type, being automatic, and being biautomatic are investigated for this class of monoids. The first main result shows that for any consistent combination of these properties and their negations, there is a homogeneous monoid with exactly this combination of properties. We then introduce the new concept of abstract Rees-commensurability (an analogue of the notion of abstract commensurability for groups) in order to extend this result to show that the same statement holds even if one restricts attention to the class of $n$-ary homogeneous monoids (where every side of every relation has fixed length $n$). We then introduce a new encoding technique that allows us to extend the result partially to the class of $n$-ary multihomogenous monoids.

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

Recommendations

• MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS
• FINITENESS CONDITIONS FOR REWRITING SYSTEMS
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• Constructing finitely presented monoids which have no finite complete presentation
• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.

zbMATH Keywords

presentationhomotopyautomaticfinite derivation typerewriting systembiautomatichomogeneous monoid

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Handbook of weighted automata
• Title not available (Why is that?)
• Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
• A new approach to the word and conjugacy problems in the braid groups
• Set-theoretical solutions to the quantum Yang-Baxter equation
• Term Rewriting and All That
• Retractability of set theoretic solutions of the Yang-Baxter equation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• NOETHERIAN SEMIGROUP ALGEBRAS
• Title not available (Why is that?)
• Notions of automaticity in semigroups.
• Plactic algebras.
• Automatic semigroups
• Structure of Chinese algebras.
• Minimal spectrum and the radical of Chinese algebras.
• THE CHINESE MONOID
• Automatic monoids and change of generators
• Fundamentals of Computation Theory
• Diagram groups
• GRÖBNER–SHIRSHOV BASIS FOR THE CHINESE MONOID
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite complete rewriting systems and finite derivation type for small extensions of monoids
• A finiteness condition for rewriting systems
• Finite homotopy bases of one-relator monoids
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• Finite derivation type for Rees matrix semigroups
• Finite derivation type for large ideals.
• ON HOMOTOPICAL AND HOMOLOGICAL FINITENESS CONDITIONS FOR FINITELY PRESENTED MONOIDS
• Title not available (Why is that?)
• On finite complete rewriting systems and large subsemigroups.
• Synchronized rational relations of finite and infinite words
• Finitely presented algebras and groups defined by permutation relations.
• Quadratic algebras of skew type and the underlying monoids.
• Finitely presented monoids and algebras defined by permutation relations of Abelian type.
• Algebras and groups defined by permutation relations of alternating type.
• Higher-dimensional categories with finite derivation type
• Higher-dimensional normalisation strategies for acyclicity
• The shifted plactic monoid
• Rewriting as a special case of non-commutative Gröbner basis theory
• Gröbner-Shirshov bases for plactic algebras.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.
• On the hypoplactic monoid
• DETERMINING IDEALS OF A GIVEN FINITE INDEX IN A FINITELY PRESENTED SEMIGROUP
• On properties not inherited by monoids from their Schützenberger groups.
• AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX
• Title not available (Why is that?)
• Gröbner bases for quadratic algebras of skew type.
• Quadratic algebras of skew type.
• Title not available (Why is that?)
• Constructing finitely presented monoids which have no finite complete presentation
• The Monoid of Queue Actions

Cited In (6)

• Complete rewriting systems and homology of monoid algebras
• Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences
• Coherence for plactic monoids via rewriting theory and crystal structures
• MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS
• Describing semigroups with defining relations of the form \(xy=yz\) and \(yx=zy\) and connections with knot theory
• Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\)

This page was built for publication: On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids

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