Confluence of the Chinese Monoid

Jörg Endrullis*, Jan Willem Klop

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

28 Downloads (Pure)

Abstract

The Chinese monoid, related to Knuth’s Plactic monoid, is of great interest in algebraic combinatorics. Both are ternary monoids, generated by relations between words of three symbols. The relations are, for a totally ordered alphabet, cba = cab = bca if a ≤ b ≤ c. In this note we establish confluence by tiling for the Chinese monoid, with the consequence that every two words u, v have extensions to a common word: ∀u, v. ∃x, y. ux = vy. Our proof is given using decreasing diagrams, a method for obtaining confluence that is central in abstract rewriting theory. Decreasing diagrams may also be applicable to various related monoid presentations. We conclude with some open questions for the monoids considered.

Original languageEnglish
Title of host publicationThe Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy
Subtitle of host publicationEssays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday
EditorsMário S. Alvim, Kostas Chatzikokolakis, Carlos Olarte, Frank Valencia
PublisherSpringer Verlag
Pages206-220
Number of pages15
ISBN (Electronic)9783030311759
ISBN (Print)9783030311742
DOIs
Publication statusPublished - 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11760 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Confluence of the Chinese Monoid'. Together they form a unique fingerprint.

Cite this