Dehornoy's ordering of braids
This is a C-program implementing the Dehornoy's algorithm discribed in
the paper
P.Dehornoy, A fast method of comparing braids, Advances in
Mathematics 125 (1997) 200-235.
The program works under UNIX (and presumably under other systems,
Windows'95, etc.).
Representation of braids
Each entrance of a
standard generator si of the braid group is
represented by its subscript
i. An entrance of the inverse generator
si-1 is represented by the
negative subscript -i. So the whole word will be represented by a
sequence of integers. For example, the word
s2-1 s32
s1-3
is represented by a list
-2 3 3 -1 -1 -1
Download the source files
Source code (gzipped tar file
"dehornoy.tar.gz")
After downloading please do the following commands:
- tar xfvz dehornoy.tar.zip (you will get a new directory
"dehornoy" with the files "braid.h", "main.c", "word.c", "wordin",
"wordout" inside it)
- cd dehornoy
- cc main.c (This is the standard C compiler in UNIX. You will get a
file "a.out")
- ./a.out
Input/Output
The file "wordin" contains a list representing the input word.
You can change the input word by editing this file with a text editor.
If you would like to reduce a single word then the list should be ended
with zero. So in the example above
it should be
-2 3 3 -1 -1 -1 0.
Another option is if you would like to compare two braids a and
b, then
the corresponding lists for a and b sould be separated by zero
(for example, -2 3 3 -1 0 -3 1 1). The result
will be reduced word for ab-1.
The file "wordout" contains a list representing the reduced word.
Related things
The paper
contains a nice geometrical description of the ordering.
Java program by Djun M. Kim drawing beautiful pictures of curve
diagrams of braids.