Quadratic normalization in monoids

DOI10.1142/S0218196716500399MaRDI QIDQ2821823zbMATH OpenFDO

Authors Patrick Dehornoy, Yves Guiraud

Publication date 23 September 2016

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

convergencenormal formnormalizationterminationChinese monoidGarside familyrewriting systemArtin-Tits monoidplactic monoid

Mathematics Subject Classification ID

Braid groups; Artin groups (20F36) Grammars and rewriting systems (68Q42) Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05)

Abstract: In the general context of presentations of monoids, we study normalisation processes that are determined by their restriction to length-two words. Garside's greedy normal forms and quadratic convergent rewriting systems, in particular those associated with the plactic monoids, are typical examples. Having introduced a parameter, called the class and measuring the complexity of the normalisation of length-three words, we analyse the normalisation of longer words and describe a number of possible behaviours. We fully axiomatise normalisations of class (4, 3), show the convergence of the associated rewriting systems, and characterise those deriving from a Garside family.

Recommendations

• Garside and quadratic normalisation: a survey
• New approaches to plactic monoid via Gröbner-Shirshov bases.
• A normal form for a class of monoids including the singular braid monoids
• Alternating normal forms for braids and locally Garside monoids.
• Characterizing the normal forms of a finitely presented monoid

Cites work

• A geometric characterization of automatic semigroups
• ALGORITHMS FOR POSITIVE BRAIDS
• Combinatorics of Coxeter Groups
• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.
• THE CHINESE MONOID

Cited in

(8)

• Automatic semigroups vs automaton semigroups
• Correspondence between factorability and normalization in monoids
• scientific article; zbMATH DE number 4163663 (Why is no real title available?)
• Automaton (semi)groups: Wang tilings and Schreier tries
• Garside and quadratic normalisation: a survey
• Plactic monoids: a braided approach
• Coherent presentations of monoids with a right-Noetherian Garside family
• Cohomology of idempotent braidings with applications to factorizable monoids

This page was built for publication: Quadratic normalization in monoids

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