TY - JOUR
T1 - Braids via term rewriting
AU - Endrullis, Jörg
AU - Klop, Jan Willem
PY - 2019/7/19
Y1 - 2019/7/19
N2 - 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.
AB - 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.
KW - Braids
KW - Confluence
KW - Decreasing diagrams
KW - Term rewriting
UR - http://www.scopus.com/inward/record.url?scp=85057960953&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057960953&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2018.12.006
DO - 10.1016/j.tcs.2018.12.006
M3 - Article
AN - SCOPUS:85057960953
SN - 0304-3975
VL - 777
SP - 260
EP - 295
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -