2019

  1. Confluence of the Chinese Monoid
    Jörg Endrullis, and Jan Willem Klop
    In: The Art of Modelling Computational Systems, pp. 206–220, Springer (2019)
    paper

    Summary

    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, if 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.

    See research for an overview of my research on confluence.

    Bibtex

    @inproceedings{confluence:chinese:monoid:2019,
  author = {Endrullis, J{\"{o}}rg and Klop, Jan Willem},
  title = {{Confluence of the Chinese Monoid}},
  booktitle = {The Art of Modelling Computational Systems},
  series = {LNCS},
  volume = {11760},
  pages = {206--220},
  publisher = {Springer},
  year = {2019},
  doi = {10.1007/978-3-030-31175-9\_12},
  keywords = {rewriting,confluence},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-030-31175-9_12
  2. Braids via Term Rewriting
    Jörg Endrullis, and Jan Willem Klop
    Theoretical Computer Science , 777 , pp. 260–295 (2019)
    paper

    Summary

    We present a brief introduction to braids, in particular simple positive braids, with a double emphasis: first, we focus on term rewriting techniques, in particular, reduction diagrams and decreasing diagrams. The second focus is our employment of the colored braid notation next to the more familiar Artin notation. Whereas the latter is a relative, position dependent, notation, the former is an absolute notation that seems more suitable for term rewriting techniques such as symbol tracing. Artin's equations translate in this notation to simple word inversions. With these points of departure we treat several basic properties of positive braids, in particular related to the word problem, confluence property, projection equivalence, and the congruence property. In our introduction the beautiful diamond known as the permutohedron plays a decisive role.

    Bibtex

    @article{rewriting:braids:2019,
  author = {Endrullis, J{\"{o}}rg and Klop, Jan Willem},
  title = {Braids via term rewriting},
  journal = {Theoretical Computer Science},
  volume = {777},
  pages = {260--295},
  year = {2019},
  doi = {10.1016/j.tcs.2018.12.006},
  keywords = {rewriting,confluence},
  type = {journal}
}

    Digital Object Identifier

    10.1016/j.tcs.2018.12.006
  3. Syllogistic Logic with "Most"
    Jörg Endrullis, and Lawrence S. Moss
    Mathematical Structures in Computer Science , 29 (6) , pp. 763–782 (2019)
    paper

    Summary

    This paper presents a sound and complete proof system for the logical system whose sentences are of the form

    • All X are Y,
    • Some X are Y, and
    • Most X are Y
    where we interpret these sentences on finite models, with the meaning of `most' being `strictly more than half'. Our proof system is syllogistic; there are no individual variables.

    This paper is an extended version of Syllogistic Logic with "Most" presented at the International Workshop on Logic, Language, Information, and Computation (WoLLIC 2015).

    Bibtex

    @article{logic:most:2019,
  author = {Endrullis, J\"{o}rg and Moss, Lawrence S.},
  title = {{Syllogistic Logic with "Most"}},
  journal = {Mathematical Structures in Computer Science},
  volume = {29},
  number = {6},
  pages = {763--782},
  year = {2019},
  doi = {10.1017/S0960129518000312},
  keywords = {logic},
  type = {journal}
}

    Digital Object Identifier

    10.1017/S0960129518000312