Braids via term rewriting

Jörg Endrullis*, Jan Willem Klop

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

9 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)260-295
Number of pages36
JournalTheoretical Computer Science
Volume777
Early online date6 Dec 2018
DOIs
Publication statusPublished - 19 Jul 2019

Keywords

  • Braids
  • Confluence
  • Decreasing diagrams
  • Term rewriting

Fingerprint

Dive into the research topics of 'Braids via term rewriting'. Together they form a unique fingerprint.

Cite this