טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFabienne Chouraqui
SubjectRewriting Systems for Alternating Knot Groups
DepartmentDepartment of Mathematics
Supervisor Professor Juhasz Arie


Abstract

The word problem was first raised by Max Dehn around 1920. Let F be a free group and let G be a quotient of F. The word problem asks for an algorithm which decides for any two given words whether their image in G coincide. This question is unsolvable in general. Yet, even when the word problem is known to be solvable, there is not necessarily an efficient algorithm that solves it.


The use of string rewriting systems has been proved to be an efficient tool for solving the word problem. A string rewriting system for a monoid (group) G can be described as a set of rules, which permit to rewrite words in the free monoid (group) F to a simpler word. The aim in this process of rewriting is to reach in a finite number of steps a word, called the normal form, which is shorter or simpler in some other sense. Thus given any two words u and v in the free group F, we find for each its normal form. If the normal forms of u and v are equal in F then the words u and v have equal images in G.

Alternating knot groups are known to have nice properties and in particular to have a word problem which is solvable. In our work, we show that the augmented Dehn presentation of the knot group of alternating knots have a complete and finite rewriting system, and hence there exists a very simple algorithm which solves the word problem.