Confluence of the Chinese Monoid

Jörg Endrullis; Jan Willem Klop

doi:10.1007/978-3-030-31175-9_12

Confluence of the Chinese Monoid

Jörg Endrullis^*, Jan Willem Klop

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-review

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 language	English
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
Publisher	Springer Verlag
Pages	206-220
Number of pages	15
ISBN (Electronic)	9783030311759
ISBN (Print)	9783030311742
DOIs	https://doi.org/10.1007/978-3-030-31175-9_12
Publication status	Published - 2019

Publication series

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

Access to Document

10.1007/978-3-030-31175-9_12

Cite this

Endrullis, J., & Klop, J. W. (2019). Confluence of the Chinese Monoid. In M. S. Alvim, K. Chatzikokolakis, C. Olarte, & F. Valencia (Eds.), The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday (pp. 206-220). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11760 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-31175-9_12

Endrullis, Jörg ; Klop, Jan Willem. / Confluence of the Chinese Monoid. The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. editor / Mário S. Alvim ; Kostas Chatzikokolakis ; Carlos Olarte ; Frank Valencia. Springer Verlag, 2019. pp. 206-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{eb0919329b524b22ada5c69162bfe9b4,

title = "Confluence of the Chinese Monoid",

abstract = "The Chinese monoid, related to Knuth{\textquoteright}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.",

author = "J{\"o}rg Endrullis and Klop, {Jan Willem}",

year = "2019",

doi = "10.1007/978-3-030-31175-9_12",

language = "English",

isbn = "9783030311742",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "206--220",

editor = "Alvim, {M{\'a}rio S.} and Kostas Chatzikokolakis and Carlos Olarte and Frank Valencia",

booktitle = "The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy",

address = "Germany",

}

Endrullis, J & Klop, JW 2019, Confluence of the Chinese Monoid. in MS Alvim, K Chatzikokolakis, C Olarte & F Valencia (eds), The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11760 LNCS, Springer Verlag, pp. 206-220. https://doi.org/10.1007/978-3-030-31175-9_12

Confluence of the Chinese Monoid. / Endrullis, Jörg; Klop, Jan Willem.

The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. ed. / Mário S. Alvim; Kostas Chatzikokolakis; Carlos Olarte; Frank Valencia. Springer Verlag, 2019. p. 206-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11760 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-review

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 -

Endrullis J, Klop JW. Confluence of the Chinese Monoid. In Alvim MS, Chatzikokolakis K, Olarte C, Valencia F, editors, The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. Springer Verlag. 2019. p. 206-220. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-31175-9_12

Confluence of the Chinese Monoid

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this