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.
|Title of host publication||The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy|
|Subtitle of host publication||Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday|
|Editors||Mário S. Alvim, Kostas Chatzikokolakis, Carlos Olarte, Frank Valencia|
|Number of pages||15|
|Publication status||Published - 2019|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|