Braids via term rewriting

Research output: Contribution to JournalArticleAcademicpeer-review

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)1-36
Number of pages36
JournalTheoretical Computer Science
DOIs
Publication statusE-pub ahead of print - 6 Dec 2018

Fingerprint

Term Rewriting
Braid
Notation
Diamonds
Diagram
Projection Property
Confluence
Word problem
Tracing
Strombus or kite or diamond
Congruence
Inversion
Equivalence
Dependent

Keywords

  • Braids
  • Confluence
  • Decreasing diagrams
  • Term rewriting

Cite this

@article{97a4d1544a1248269ce88c312c6f9c18,
title = "Braids via term rewriting",
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.",
keywords = "Braids, Confluence, Decreasing diagrams, Term rewriting",
author = "J{\"o}rg Endrullis and Klop, {Jan Willem}",
year = "2018",
month = "12",
day = "6",
doi = "10.1016/j.tcs.2018.12.006",
language = "English",
pages = "1--36",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Braids via term rewriting. / Endrullis, Jörg; Klop, Jan Willem.

In: Theoretical Computer Science, 06.12.2018, p. 1-36.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Braids via term rewriting

AU - Endrullis, Jörg

AU - Klop, Jan Willem

PY - 2018/12/6

Y1 - 2018/12/6

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

SP - 1

EP - 36

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -