TY - CHAP
T1 - Confluence of the Chinese Monoid
AU - Endrullis, Jörg
AU - Klop, Jan Willem
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85075078296&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85075078296&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-31175-9_12
DO - 10.1007/978-3-030-31175-9_12
M3 - Chapter
AN - SCOPUS:85075078296
SN - 9783030311742
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 206
EP - 220
BT - The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy
A2 - Alvim, Mário S.
A2 - Chatzikokolakis, Kostas
A2 - Olarte, Carlos
A2 - Valencia, Frank
PB - Springer Verlag
ER -