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

DOI10.1016/J.IC.2017.05.003MaRDI QIDQ2013556zbMATHOpenAlexFDO

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

Publication date 8 August 2017

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

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

zbMATH Keywords

presentationhomotopyautomaticfinite derivation typerewriting systembiautomatichomogeneous monoid

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Semigroups in automata theory, linguistics, etc. (20M35)

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.

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.

Cites work

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

Cited in

(7)

• MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS
• Complete rewriting systems and homology of monoid algebras
• Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences
• 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}\)
• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.
• Describing semigroups with defining relations of the form \(xy=yz\) and \(yx=zy\) and connections with knot theory
• Coherence for plactic monoids via rewriting theory and crystal structures

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)