The aim of this book is to present recently discovered connections between Artin's braid groups En and left self-distributive systems (also called LD systems), which are sets equipped with a binary operation satisfying the left self-distributivity identity x(yz) = (xy)(xz). (LD) Such connections appeared in set theory in the 1980s and led to the discovery in 1991 of a left invariant linear order on the braid groups. Braids and self-distributivity have been studied for a long time. Braid groups were introduced in the 1930s by E. Artin, and they have played an increas ing role in mathematics in view of their connection with many fields, such as knot theory, algebraic combinatorics, quantum groups and the Yang-Baxter equation, etc. LD-systems have also been considered for several decades: early examples are mentioned in the beginning of the 20th century, and the first general results can be traced back to Belousov in the 1960s. The existence of a connection between braids and left self-distributivity has been observed and used in low dimensional topology for more than twenty years, in particular in work by Joyce, Brieskorn, Kauffman and their students. Brieskorn mentions that the connection is already implicit in (Hurwitz 1891). The results we shall concentrate on here rely on a new approach developed in the late 1980s and originating from set theory."

This is the award-winning monograph of the Sunyer i Balaguer Prize 1999. The book presents recently discovered connections between Artin s braid groups and left self-distributive systems, which are sets equipped with a binary operation satisfying the identity x(yz) = (xy)(xz). Although not a comprehensive course, the exposition is self-contained, and many basic results are established. In particular, the first chapters include a thorough algebraic study of Artin s braid groups."

Everyone knows what braids are, whether they be made of hair, knitting wool, or electrical cables. However, it is not so evident that we can construct a theory about them, i.e. to elaborate a coherent and mathematically interesting corpus of results concerning them. This book demonstrates that there is a resoundingly positive response to this question: braids are fascinating objects, with a variety of rich mathematical properties and potential applications. A special emphasis is placed on the algorithmic aspects and on what can be called the 'calculus of braids', in particular the problem of isotopy. Prerequisites are kept to a minimum, with most results being established from scratch. An appendix at the end of each chapter gives a detailed introduction to the more advanced notions required, including monoids and group presentations. Also included is a range of carefully selected exercises to help the reader test their knowledge, with solutions available.

Everyone knows what braids are, whether they be made of hair, knitting wool, or electrical cables. However, it is not so evident that we can construct a theory about them, i.e. to elaborate a coherent and mathematically interesting corpus of results concerning them. This book demonstrates that there is a resoundingly positive response to this question: braids are fascinating objects, with a variety of rich mathematical properties and potential applications. A special emphasis is placed on the algorithmic aspects and on what can be called the 'calculus of braids', in particular the problem of isotopy. Prerequisites are kept to a minimum, with most results being established from scratch. An appendix at the end of each chapter gives a detailed introduction to the more advanced notions required, including monoids and group presentations. Also included is a range of carefully selected exercises to help the reader test their knowledge, with solutions available.

Cet ouvrage presente les bases de la theorie de la complexite des algorithmes et en derive les theoremes fondamentaux de decidabilite et d'indecidabilite pour la logique et l'arithmetique, dont le premier theoreme d'incompletude de Godel. En faisant reposer toutes les preuves sur le codage de l'arret d'une machine de Turing, on a souligne l'homogeneite et l'unite profonde des resultats presentes. L'approche par les machines de Turing est tres accessible grace a la familiarite donnee aujourd'hui par l'informatique. Le livre n'est pas une encyclopedie exhaustive, mais parvient de facon rapide a demontrer un choix de resultats representatifs de l'ensemble de la theorie.