Patrick Dehornoy

Patrick Dehornoy

Articles de recherche / Research articles

From newer to older; surveys are on a different page.
(with Emilie TESSON) Garside combinatorics for Thompson's monoid F+ and a hybrid with the braid monoid Binfty+, Algebraic Combinat., to appear, arXiv:1803.02639, pdf file

On the model of simple braids, defined to be the left divisors of Garside's elements Delta_n in the monoid Binfty+, we investigate simple elements in Thompson's monoid F+ and in a larger monoid H+ that is a hybrid of Binfty+ and F+: in both cases, we count how many simple elements left divide the right lcm of the first n - 1 atoms, and characterize their normal forms in terms of forbidden factors. In the case of H+, a generalized Pascal triangle appears.

A cancellativity criterion for presented monoids, arXiv:1802.04607, Semigroup Forum, to appear (18 pages), pdf file

We establish a new, fairly general cancellativity criterion for a presented monoid that properly extends the previously known related criteria. It is based on a new version of the word transformation called factor reversing, and its specificity is to avoid any restriction on the number of relations in the presentation. As an application, we deduce the cancellativity of some natural extension of Artin's braid monoid in which crossings are colored.

(with Derek HOLT and Sarah REES) Multifraction reduction IV: Padding and Artin-Tits groups of sufficiently large type, arXiv:1701.06413, J. Pure Appl. Algebra 222 (2018) 4082-4098, pdf file

We investigate the padded version of reduction, an extension of multifraction reduction as defined in arXiv:1606.08991, and connect it both with ordinary reduction and with the so-called Property H. As an application, we show that all Artin-Tits groups of sufficiently large type satisfy some weakening Conjecture Apadded of Conjecture A, thus showing that the reduction approach is relevant for these groups.

(with Friedrich WEHRUNG) Multifraction reduction III: The case of interval monoids, arXiv:1606.09018, J. Comb. Algebra 1 (2017) 341-370, pdf file

We investigate gcd-monoids, which are cancellative monoids in which any two elements admit a left- and a right-gcd, and the associated reduction of multifractions (arXiv:1606.08991), a general approach to the Word Problem for the enveloping group. Here we consider the particular case of interval monoids associated with finite posets. In this way, we construct gcd-monoids, in which reduction of multifractions has prescribed properties not yet known to be compatible: semi-convergence of reduction without convergence, semi-convergence up to some level but not beyond, non-embeddability into the enveloping group (a strong negation of semi-convergence).

Multifraction reduction II: Conjectures for Artin-Tits groups, arXiv:1606.08995, J. Comb. Algebra 1 (2017) 229-287, pdf file

Multifraction reduction is a new approach to the Word Problem for Artin-Tits groups and, more generally, for the enveloping group U(M) of a monoid M in which any two elements admit a greatest common divisor. This approach is based on a rewrite system R(M) that extends free group reduction. In this paper, we show that for R(M) to satisfy a weak form of convergence called semi-convergence is sufficient for solving the Word Problem for U(M), and we connect semi-convergence with other conditions involving R(M). We conjecture that all these properties are valid when M is an Artin-Tits monoid, and report about numerical experiments supporting this conjecture.

Multifraction reduction I: The 3-Ore case and Artin-Tits groups of type FC, arXiv:1606.08991, J. Comb. Algebra 1 (2017) 185-228, pdf file

We describe a new approach to the Word Problem for Artin-Tits groups and, more generally, for the enveloping group U(M) of a monoid M in which any two elements admit a greatest common divisor. The method relies on a rewrite system R(M) that extends free reduction for free groups. Here we show that, if M satisfies what we call the 3-Ore condition about common multiples, what corresponds to type FC in the case of Artin-Tits monoids, then the system R(M) is convergent. Under this assumption, we obtain a unique representation result for the elements of U(M), extending Ore's theorem for groups of fractions and leading to a solution of the Word Problem of a new type. We also show that there exist universal shapes for the van Kampen diagrams of the words representing 1.

(with Yves GUIRAUD) Quadratic normalisation in monoids, arXiv:1504.02717, Intern. J. Algebra Comput. 26-5 (2016) 935-972, pdf file

In the general context of presentations of monoids, we study normalisation processes that are determined by their restriction to length-two words. Garside's greedy normal forms and quadratic convergent rewriting systems, in particular those associated with the plactic monoids, are typical examples. Having introduced a parameter called the class measuring the complexity of the normalisation of length-three words, we analyse the normalisation of longer words and describe a number of possible behaviours. We fully axiomatise normalisations of class (4, 3), show the convergence of the associated rewriting systems, and characterise those deriving from a Garside family.

(with François DIGNE, Eddy GODELLE, Daan KRAMMER, and Jean MICHEL) Addenda to "Foundations of Garside Theory", arXiv:1412.5299, (45 pages), pdf file

This text consists of additions to the book "Foundations of Garside Theory'', EMS Tracts in Mathematics, vol. 22 (2015) - see introduction and table of contents in arXiv:1309.0796 - namely skipped proofs and solutions to selected exercises.

(with Matthew DYER and Christophe HOHLWEG) Garside families in Artin-Tits monoids and low elements in Coxeter groups, arXiv: 1411.7498, Comptes-Rendus Math. 353 (2015) 403-408, pdf file

(MSC 20F36, 20F55) We show that every finitely generated Artin-Tits group admits a finite Garside family, by introducing the notion of a low element in a Coxeter group and proving that the family of all low elements in a Coxeter system (W, S) with S finite includes S and is finite and closed under suffix and join with respect to the right weak order.

(with Philippe BIANE) Dual Garside structure of braids and free cumulants of products, arXiv: 1407.1604, Sém. Lothar. Combin. 72 (2014) Article B72b, 15 pp.,, pdf file

(MSC 20F36, 05A17, 46L54) We count the n-strand braids whose normal decomposition has length at most two in the dual braid monoid B_n+* by reducing the question to a computation of free cumulants for a product of independent variables, for which we establish a general formula.

Set-theoretic solutions of the Yang-Baxter equation, RC-calculus, and Garside germs, arXiv 1403.3019, Adv. in Math. 282 (2015) 93-127, pdf file

(MSC 20N02, 20F38, 20M30, 20F55, 57M25) Building on a result by W. Rump, we show how to exploit the right-cyclic law (x.y).(x.z) = (y.x).(y.z) in order to investigate the structure groups and monoids attached with (involutive nondegenerate) set-theoretic solutions of the Yang-Baxter equation. We develop a sort of right-cyclic calculus, and use it to obtain short proofs for the existence both of the Garside structure and of the I-structure of such groups. We describe finite quotients that exactly play for the considered groups the role that Coxeter groups play for Artin-Tits groups.

(with Victoria LEBED) Two- and three-cocycles for Laver tables, arXiv:1401.2335, J. Knot Th. and Ramifications 23-4 (2014) 1450017, pdf file

(MSC 57M27, 17D99, 20N02, 55N35, 06A99) We determine all 2- and 3-cocycles for Laver tables, an infinite sequence of finite structures obeying the left-selfdistributivity law; in particular, we describe simple explicit bases. This provides a number of new positive braid invariants and paves the way for further potential topological applications. Incidentally, we establish and study a partial ordering on Laver tables given by the right-divisibility relation.

(with François DIGNE, Eddy GODELLE, Daan KRAMMER, and Jean MICHEL) Foundations of Garside Theory, arXiv:1309.0796, Unpublished (21 pages), pdf file

(MSC 20F36, 05A05, 18B40, 20B30, 20F10, 20F38, 20F55, 20M05, 20N02, 68Q17) This text consists of the introduction, table of contents, and bibliography of a long manuscript (703 pages) that is currently submitted for publication. This manuscript develops an extension of Garside's approach to braid groups and provides a unified treatment for the various algebraic structures that appear in this context. The complete text can be found at

Coxeter-like groups for groups of set-theoretic solutions of the Yang-Baxter equation, arXiv:1305.3900, Comptes Rendus Mathematiques 351 (2013) 419-424, pdf file

(MSC 20F38, 20F55) We attach with every finite, involutive, nondegenerate set-theoretic solution of the Yang-Baxter equation a finite group that plays for the associated structure group the role that a finite Coxeter group plays for the associated Artin-Tits group.

(with Volker Gebhardt) Algorithms for Garside calculus, arXiv:1301.3277, J. Symbol. Comput. 63 (2014) 68-116, pdf file

(MSC 20F10, 18B40, 20F36, 68Q17) Garside calculus is the common mechanism that underlies a certain type of normal form for the elements of a monoid, a group, or a category. Originating from Garside's approach to Artin's braid groups, it has been extended to more and more general contexts, the latest one being that of categories and what are called Garside families. One of the benefits of this theory is to lead to algorithms solving effectively the naturally occurring problems, typically the Word Problem. The aim of this paper is to present and solve these algorithmic questions in the new extended framework.

(with François DIGNE and Jean MICHEL) Garside families and Garside germs, arXiv:1208.3362, J. of Algebra 380 (2013) 109-145, pdf file

(MSC 20M05, 18B40, 20F10, 20F36) Garside families have recently emerged as a relevant context for extending results involving Garside monoids and groups, which themselves extend the classical theory of (generalized) braid groups. Here we establish various characterizations of Garside families, that is, equivalently, various criteria for establishing the existence of normal decompositions of a certain type.

Monoids of O-type, subword reversing, and ordered groups, arXiv:1204.3211, Journal of Group Theory 17-3 (2014) 465-524, pdf file

(MSC 06F15, 20M05, 20F60) We describe a simple scheme for constructing finitely generated monoids in which left-divisibility is a linear ordering and for practically investigating these monoids. The approach is based on subword reversing, a general method of combinatorial group theory, and connected with Garside theory, here in a non-Noetherian context. As an application we describe several families of ordered groups whose space of left-invariant orderings has an isolated point, including torus knot groups and some of their amalgamated products.

Tamari Lattices and the symmetric Thompson monoid, arXiv:1109.5296; in: Associahedra, Tamari lattices, and Related Structures, F.Mueller-Hoissen, J.Pallo, J.Stasheff, H.O.Walther eds, Progress in Math. vol. 299, Birkhauser (2012) pp. 211-250, pdf file

(MSC 06B10, 06F15, 20F38, 20M05) We investigate the connection between Tamari lattices and the Thompson group F, summarized in the fact that F is a group of fractions for a certain monoid F+sym whose Cayley graph includes all Tamari lattices. Under this correspondence, the Tamari lattice operations are the counterparts of the least common multiple and greatest common divisor operations in F+sym. As an application, we show that, for every n, there exists a length l chain in the nth Tamari lattice whose endpoints are at distance at most 12l/n.

(with Eddy GODELLE) A conjecture about Artin-Tits groups, arXiv:1110.3600, J. Pure Appl. Algebra 217 (2013) 741-756, pdf file

(MSC 20B30, 20F55, 20F36) We conjecture that the word problem of Artin-Tits groups can be solved without introducing trivial factors ss^{-1} or s^{-1}s. Here we make this statement precise and explain how it can be seen as a weak form of hyperbolicity. We prove the conjecture in the case of Artin-Tits groups of type FC, and we discuss various possible approaches for further extensions, in particular a syntactic argument that works at least in the right-angled case.

Combinatorial distance between braid words, arXiv:0906.3814, Unpublished note (4 pages), pdf file

(MSC 20F36) We give a simple naming argument for establishing lower bounds on the combinatorial distance between (positive) braid words.

(with Marc AUTORD) On the distance between the expressions of a permutation, arXiv:0902.3074, Europ. J. Combinat. 31 (2010) 1829-1846, pdf file

(MSC: 20B30, 05E15, 20F55, 20F36) We prove that the combinatorial distance between any two reduced expressions of a given permutation of {1, ..., n} in terms of transpositions lies in O(n^4). We prove that this bound is sharp, and, using a connection with the intersection numbers of certain curves in van Kampen diagrams, we give a practical criterion for proving that the derivations provided by the reversing algorithm of [Dehornoy, JPAA 116 (1997) 115-197] are optimal. We also show the existence of length l expressions whose reversing requires C l^4 elementary steps.

On the rotation distance between binary trees, arXiv:0901.2557, Advances in Math., 223-4 (2010) 1316-1355, pdf file

(MSC: 05C12, 20F38, 52B20) We develop combinatorial methods for computing the rotation distance between binary trees, i.e., equivalently, the flip distance between triangulations of a polygon. As an application, we prove that, for each n, there exist size n trees at distance 2n - O(sqrt(n)).

Left-Garside categories, self-distributivity, and braids, arXiv:0810.4698, Ann. Math. Blaise Pascal, 16 (2009) 189-244, pdf file

(MSC: 18B40, 20N02, 20F36) In connection with the emerging theory of Garside categories, we develop the notions of a left-Garside category and of a locally left-Garside monoid. In this framework, the relationship between the self-distributivity law LD and braids amounts to the result that a certain category associated with LD is a left-Garside category, which projects onto the standard Garside category of braids. This approach leads to a realistic program for establishing the Embedding Conjecture of [Dehornoy, Braids and Self-distributivity, Birkhauser (2000), Chap. IX].

(with Lorenzo CARLUCCI and Andreas WEIERMANN) Unprovability results involving braids, arXiv:0711.3785, Proc. London Math. Soc., 102-1 (2011) 159-192, pdf file

(MSC: 03B30, 03F35, 20F36, 91A50) We construct long sequences of braids that are descending with respect to the standard order of braids (``Dehornoy order''), and we deduce that, contrary to all usual algebraic properties of braids, certain simple combinatorial statements involving the braid order are true, but not provable in the subsystems ISigma1 or ISigma2 of the standard Peano system.

Alternating normal forms in braid monoids and locally Garside monoids, arXiv:0702.592, J. Pure Appl. Algebra, 212-11 (2008) 2416-2439, pdf file

(MSC: 20F36, 20M05, 06F05) We describe new types of normal forms for braid monoids, Artin-Tits monoids, and, more generally, all monoids in which divisibility has some convenient lattice properties (``locally Garside monoids''). We show that, in the case of braids, one of these normal forms turns out to coincide with the normal form introduced by Burckel and deduce that the latter can be computed easily. This approach leads to a new, simple description for the canonical well-order of B_n+ in terms of that of B_(n-1)+.

(with Vincent VAN OOSTROM) Using groups for investigating rewrite systems, Math. Struct. in Comp. Sci., 18 (2008) 1133-1167, pdf file

(MSC: 68Q01, 68Q42, 20N02) We describe several technical tools that prove to be efficient for investigating the rewrite systems associated with an equational specification. These tools consist in introducing a monoid of partial maps, listing the monoid relations corresponding to the local confluence diagrams of the rewrite system, then introducing the group presented by these relations, and finally replacing the initial rewrite system with a internal process entirely sitting in the latter group. When the approach can be completed, one typically obtains a practical method for constructing algebras satisfying prescribed equations and for solving the associated word problem. The above techniques have been developed by the first author in a context of general algebra. The goal of this paper is to bring them to the attention of the rewrite system community. We hope that such techniques can be useful for more general rewrite systems.

Using shifted conjugacy in braid-based cryptography, Contemp. Math. 418 (2006) 65-73, pdf file

(MSC: 94A60, 94A62, 68P25, 20F36) Conjugacy is not the only possible primitive for designing braid-based protocols. To illustrate this principle, we describe a Fiat-Shamir-style authentication protocol that be can be implemented using any binary operation that satisfies the left self-distributive law. Conjugation is an example of such an operation, but there are other examples, in particular the shifted conjugation on Artin's braid group B_oo, and the finite Laver tables. In both cases, the underlying structures have a high combinatorial complexity, and they lead to difficult problems.

Free augmented LD-systems, J. Algebra and Applications, 6-1 (2007) 173-187, pdf file

(MSC: 20N02, 20F36) Define an augmented LD-system, or ALD-system, to be a set equipped with two binary operations, one satisfying the left self-distributivity law x*(y*z) = (x*y)*(x*z) and the other satisfying the mixed laws (xoy)*z = x*(y*z) and x*(yoz) = (x*y)o(x*z). We solve the word problem of the ALD laws, and prove that every element in the parenthesized braid group B• of [2, 3, 5, 6] generates a free ALD-system of rank 1, i.e., that B• is a torsion-free ALD-system.

Combinatorics of normal sequences of braids, J. Combinat. Th. Series A, 114 (2007) 389-409, pdf file

(MSC: 20F36, 05A05) Many natural counting problems arise in connection with the normal form of braids--and seem to have not been much considered so far. Here we solve some of them. One of the noteworthy points is that a number of different induction schemes appear. The key technical ingredient is an analysis of the normality condition in terms of permutations and their descents, in the vein of the Solomon algebra. As was perfectly summarized by a referee, the main result asserts that the size of the automaton involved in the automatic structure of B_n associated with the normal form can be lowered from n! to p(n), the number of partitions of n.

Still another approach to the braid ordering, Pacific J. of Math., 232-1 (2007) 139-176, pdf file

(MSC: 20F36, 05A05, 20F60) We develop a new approach to the linear ordering of the braid group B_n, based on investigating its restriction to the set Div(Delta_n^d) of all divisors of Delta_n^d in the monoid B_\infty^+, i.e., to positive n-braids whose normal form has length at most d. In the general case, we compute several numerical parameters attached with the finite orders (Div(Delta_n^d), <). In the case of 3 strands, we moreover give a complete description of the increasing enumeration of (Div(Delta_3^d), <). We deduce a new and specially direct construction of the ordering on B_3, and a new proof of the result that its restriction to B_3^+ is a well-ordering of ordinal type omega^omega.

(with Bert WIEST) On word reversing in braid groups, Int. Journal for Algebra and Computation, 16-5 (2006) 941-957, pdf file

(MSC: 20F36, 20F05, 20F10) It has been conjectured that in a braid group, or more generally in a Garside group, applying any sequence of monotone equivalences and word reversings can increase the length of a word by at most a linear factor depending on the group presentation only. We give a counter-example to this conjecture, but, on the other hand, we establish length upper bounds for the case when only right reversing is involved. We also state a new conjecture which would, like the above one, imply that the space complexity of the handle reduction algorithm is linear.

The group of parenthesized braids, Advances in Mathematics, 205 (2006) 354-409, pdf file

(MSC: 20F05, 20N02, 57M25, 57S05) We investigate a group B_• that includes Artin's braid group B_infty and Thompson's group F. The elements of B_• are represented by braids diagrams in which the distances between the strands are not uniform and, besides the usual crossing generators, new rescaling operators shrink or strech the distances between the strands. We prove that B_• is a group of fractions, that it is orderable, admits a non-trivial self-distributive structure, i.e., one involving the law x(yz)=(xy)(xz), it embeds in the mapping class group of a sphere with a Cantor set of punctures, and that Artin's representation of B_infty into the automorphisms of a free group extends to B_•.

Geometric presentations for Thompson's groups, J. Pure Appl. Algebra, 203 (2005) 1-44, pdf file

(MSC: 20F05, 20F36, 20B07) We prove that Thompson's groups F and V are the geometry groups of associativity, and of associativity together with commutativity, respectively. We deduce new presentations of F and V. These presentations lead to considering a certain subgroup of V and an extension of this subgroup. We prove that the latter are the geometry groups of associativity together with the law x(yz) = y(xz), and of associativity together with a twisted version of this law involving self-distributivity, respectively.

The group of fractions of a torsion free lcm monoid is torsion free, J. of Algebra, 281-1 (2004) 303-305, pdf file

(MSC: 20F05, 20F36) We improve and shorten the argument given in [Journal of Algebra, vol. 210 (1998) pp 291-297]. In particular, the fact that Artin braid groups are torsion free now follows from Garside's results almost immediately.

Disks in trivial braid diagrams, Topology, 43-5 (2004) 1067-1079, pdf file

(MSC: 57M25, 20F36) We show that every trivial 3-strand braid diagram contains a disk, defined as a ribbon ending in opposed crossings. Under a convenient algebraic form, the result extends to every Artin-Tits group of type I_2(m), but it fails to extend to braids with 4 strands and more. The proof uses a partition of the Cayley graph and a continuity argument.

(with Herve SIBERT and Marc GIRAULT) Entity authentication schemes using braid word reduction, Discrete Applied Math., 154-2 (2006) 420-436, pdf file

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced. A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.

Complete positive group presentations, J. of Algebra, 268 (2003) 156-197, pdf file

(MSC: 05C25, 20F36, 68Q42) A combinatorial property of positive group presentations, called completeness, is introduced, with an effective criterion for recognizing complete presentations, and an iterative method for completing an incomplete presentation. We show how to directly read several properties of the associated monoid and group from a complete presentation: cancellativity or existence of common multiples in the case of the monoid, or isoperimetric inequality in the case of the group. In particular, we obtain a new criterion for recognizing that a monoid embeds in a group of fractions. Typical presentations eligible for the current approach are the standard presentations of the Artin groups and the Heisenberg group.

Thin groups of fractions, Contemp. Math., 296 (2002) 95-128, pdf file

(MSC: 05C25, 20F36, 68Q42) A number of properties of spherical Artin groups extend to Garside groups, defined as the groups of fractions of monoids where least common multiples exist, there is no nontrivial unit, and some additional finiteness conditions are satisfied. Here we investigate a wider class of groups of fractions, called thin, which are those associated with monoids where minimal common multiples exist, but they are not necessarily unique. Also, we allow units in the involved monoids. The main results are that all thin groups of fractions satisfy a quadratic isoperimetric inequality, and that, under some additional hypotheses, they admit an automatic structure.

(with Yves LAFONT) Homology of Gaussian groups, Annales Inst. Fourier, 53-2 (2003) 489-540, pdf file

(MSC: 20J06, 18G35, 20M50, 20F36) We describe new combinatorial methods for constructing an explicit free resolution of Z by Z[G]-modules when G is a group of fractions of a monoid where enough least common multiples exist (``locally Gaussian monoid''), and, therefore, for computing the homology of G. Our constructions apply in particular to all Artin groups of finite Coxeter type, so, as a corollary, they give new ways of computing the homology of these groups.

Groupes de Garside, Ann. Sc. Ec. Norm. Sup., 35 (2002) 267-306, fichier pdf

(MSC: 05C25, 20F36, 68Q42) Define a Garside monoid to be a cancellative monoid where right and left lcm's exist and that satisfy additional finiteness assumptions, and a Garside group to be the group of fractions of a Garside monoid. The family of Garside groups contains the braid groups, all spherical Artin groups, and various generalizations previously considered. Here we prove that Garside groups are biautomatic, and that being a Garside group is a recursively enumerable property, i.e., there exists an algorithm constructing the (infinite) list of all small Gaussian groups. The latter result relies on an effective, tractable method for recognizing those presentations that define a Garside monoid.

Study of an identity, Algebra Universalis, 48 (2002) 223-248, pdf file

(MSC: 03D40, 08B20, 20N02) We solve the word problem of the identity x(yz) = (xy)(yz) by investigating a certain group describing the geometry of that identity. We also construct a concrete realization of the free system of rank 1 relative to the above identity.

The group of self-distributivity is orderable, Comm Math. Helvetici, 76 (2001) 161-182, pdf file

(AMS: 20F60, 20E08, 20N02) We prove that the group of left self-distributivity, a cousin of Thompson's group $F$ and an extension of Artin's braid group $B_\infty$ that describes the geometry of the identity $x(yz) = (xy)(xz)$, admits a bi-invariant linear ordering. To this end, we define a partial action of this group on finite binary trees that preserves a convenient linear ordering.

The geometry monoid of left self-distributivity, J. Pure Appl. Algebra, 160 (2001) 123-156, pdf file

(AMS: 20F36, 20N02) We develop a counterpart to Garside's analysis of the braid monoid $B_n^+$ relevant for the monoid $\MLD$ that describes the geometry of the left self-distributivity identity. The monoid $\MLD$ extends $B_\infty^+$, of which it shares many properties, with the exception that it has no natural expression as a direct limit of finitely generated monoids. We introduce a convenient local version of the fundamental words $\D_n$, and prove that right lower common multiples exist in $\MLD$.

The fine structure of LD-equivalence, Advances in Math 155 (2000) 264-316, pdf file

(AMS: 20N02, 20F36) Here we introduce new algebraic techniques for the study of left self-distributivity. We establish a selfsimilarity propriety for the terms $\der^k t$ which are counterparts to Garside's fundamental braids $\D_n^k$, and deduce partial answers to several long-standing open questions: convergence of the Polish Algorithm, computation of the normal form, existence of a lattice structure on LD-equivalence classes.

On the completeness of word reversing, Discrete Math., 225 (2000) 93-119, pdf file

(AMS: 05C25, 20M05, 68Q42) Word reversing is a combinatorial operation on words that detects pairs of equivalent words in monoids that admit a presentation of a certain form. Here we give conditions for this method to be complete in the sense that every pair of equivalent words can be detected by word reversing. In addition, we obtain explicit upper bounds on the complexity of the process. As an application, we show that Artin groups of Coxeter type $B$ embed into Artin groups of type $A$ and are left orderable.

Strange questions about braids, J. Knot Theory and its Ramifications, 8-5 (1999) 589-620, pdf file

(AMS: 20F36) The infinite braid group B_\infty admits a left self-distributive structure. In particular, it includes a free monogenerated left self-distributive system, and, therefore, it inherits the properties of the latter algebraic object. Here we discuss how such properties translate into the language of braids. We state new results about braids and propose a list of open questions.

Gaussian groups are torsion free, J. of Algebra, 210 (1998) 291-297, pdf file

(AMS: 20F05, 20F36) Assume that G is a group of fractions of a monoid where lower common multiples exist and where divisibility relations have no infinite descending chain. Then G is torsion free. This result applies in particular to all finite Coxeter type Artin groups.

A conjecture about conjugacy in free groups, Discuss. Math., 19 (1999) 75-112, pdf file

(AMS: 20E05, 20N02, 20F12, 68R15) Say that an element of a free group is a pure conjugate if it can be expressed from the generators using exclusively the conjugacy operation. We study free reductions in words representing pure conjugates. Using finite state automata, we attribute to the letters in such words levels that live in some free left distributive system. If a certain conjecture about this system is true, then reduction can occur only between letters lying on the same level. Under this conjecture, we establish restrictions on the form of those identities satisfied by group conjugacy, and we construct unique normal forms for large families of pure conjugates. We also show how to use group conjugacy to solve a problem related to the word problem of left self-distributivity.

(with Luis Paris) Gaussian groups and Garside groups: two generalizations of Artin groups, Proc. London Math. Soc., 79 (1999) 569-604, pdf file

(AMS: 20F05, 20F36, 20B40, 20M05) It is known that a number of algebraic properties of the braid groups extend to arbitrary finite Coxeter type Artin groups. Here we show how to extend the results to more general groups that we call Garside groups. Define a Gaussian monoid to be a finitely generated cancellative monoid where the expressions of a given element have bounded lengths, and where left and right lower common multiples exist. A Garside monoid is a Gaussian monoid in which the left and right l.c.m.'s satisfy an additional symmetry condition. A Gaussian group and a Garside group are respectively the group of fractions of a Gaussian monoid and of a Garside monoid. Braid groups and, more generally, finite Coxeter type Artin groups are Garside groups. We determine algorithmic criterions in terms of presentations for recognizing Gaussian and Garside monoids and groups, and exhibit infinite families of such groups. We describe simple algorithms that solve the word problem in a Gaussian group, show that theses algorithms have a quadratic complexity if the group is a Garside group, and prove that Garside groups have quadratic isoperimetric inequalities. We construct normal forms for Gaussian groups, and prove that, in the case of a Garside group, the language of normal forms is regular, symmetric, and geodesic, has the 5-fellow traveller property, and has the uniqueness property. This shows in particular that Garside groups are geodesically fully biautomatic. Finally, we consider an automorphism of a finite Coxeter type Artin group derived from an automorphism of its defining Coxeter graph, and prove that the subgroup of elements fixed by this automorphism is also a finite Coxeter type Artin group that can be explicitely determined.

Zeropotent left distributive systems, Comm. in Algebra 26-6 (1998) 1967-1978

(AMS: 20N02) We prove a result conjectured by J. Jezek, namely that a zeropotent left self-distributive system need not be 3-trivial, i.e., the identity x(yz) = 0 does not follow from the identities x(yz)=(xy)(xz), xx = 0 and x0 = 0x = 0. The argument is a general scheme possibly working for various identities in the context of self-distributivity.

(with Abderrahim Marzouk) Theorem proving by chain resolution, Theor. Comp. Sci., 206 (1998) 163-180

(AMS: 38T15, 03B35) Starting from the intuition given by Wu's algorithm for the resolution of polynomial systems, we construct new efficient resolution strategies for propositional clauses.

Multiple left distributive systems, Comm. Math. Univ. Carol., 38-4 (1997) 615-625

(AMS: 20N02) We describe the free objects in the variety of algebras involving several mutually distributive binary operations. Also, we show how an associative operation can be constructed on such systems in good cases, thus obtaining a two way correspondence between LD-monoids (sets with a left self-distributive and a compatible associative operation) and multi-LD-systems (sets with a family of mutually distributive operations).

Transfinite braids and left distributive operations, Math. Zeitschr., 228 (1998) 405-433, pdf file

(AMS: 20F36, 20N02) By completing Artin's braid group B_\infty with some limit points (with respect to a natural topology), we obtain an extended monoid where new left self-distributive operations are defined. This construction provides in particular effective realizations for free algebraic systems involving a left distributive operation and a compatible associative product.

Three-dimensional realizations of braids, J. London Math. Soc., 60-2 (1999) 108-132, pdf file

(AMS: 20F36, 57M25) Let us consider a standard braid diagram as a three-dimensional figure viewed from the top; what happens when we look at this figure from the side? We can obtain a new braid, and studying the connection between the initial braid and the derived braid provides a geometrical interpretation and a very simple proof for the existence of the right greedy normal form of positive braids.

A fast method for comparing braids, Advances in Math., 125 (1997) 200-235, pdf file

(AMS: 20F36, 20M05, 57M05) We describe a new method for comparing braid words which relies both on the automatic structure of the braid groups and on the existence of a linear ordering on braids. This syntactical algorithm is a direct generalization of the classical word reduction used in the description of free groups, and it is more efficient than all previously known methods.

Construction of left distributive operations and charged braids, Int. J. Algebra & Computation, 10-1 (2000) 173-190, pdf file

(AMS: 08B20, 20N02, 20F36) We show how operations satisfying the left distributivity identity can be constructed using a convenient structure monoid that describes the geometry of that identity. We finally obtain a realization of the free left distributive systems inside some extension of Artin's braid group with a very simple geometric interpretation.

An associative law on monogenic left distributive systems, Comm. Math. Univ. Carolinae, 36-1 (1995) 1-6
On the syntactic algorithm for the word problem of left distributivity, Algebra Universalis, 37 (1997) 191-222

(AMS: 20N02, 68Q42) Here we investigate the `natural' syntactic algorithm for the word problem of left distributivity, and we establish a sufficient condition which explains the convergence for all terms of a reasonable size. An algorithm for left division is also constructed.

Non-commutative versions of the Burau representation, C. R. Acad. Roy. Sci. Canada, 17-1 (1995) 53-58
Weak faithfulness properties for the Burau representation, Topol and Appl., 69 (1996) 121-143, pdf file

(AMS: 20F36, 20H25, 15A24, 57M05) We study the components of the matrices that belong to the image of the Burau representation of braids, and establish both algebraic and order constraints for a given Laurent polynomial possibly be a component of such a Burau matrix. As an application partial faithfulness results for the Burau representation are deduced.

The structure group for the associativity identity, J. Pure Appl. Algebra, 111 (1996) 59-82, pdf file

(AMS: 08A05, 20L10, 20M50) A group of elementary associativity operators is introduced so that the bracketing graphs which are the skeletons of Stasheff's associahedra become orbits and can be constructed as subgraphs of the Cayley graph of this group. A very simple proof of Mac Lane's coherence theorem is given, as well as an oriented version of this result. We also sketch a more general theory and compare the cases of associativity and left selfdistributivity.

Groups with a complemented presentation, J. Pure Appl. Algebra 116 (1997) 115-137, pdf file

(AMS: 20M05, 20F36) Let G be a group given by a presentation. We study the decomposition of the elements of G as quotients of ``positive'' elements (the elements of G that can be expressed without using the inverses of the generators) in the special case when the presentation satisfies some syntactical condition. This approach works in particular for Artin's braid groups, and results in a very simple quadratic algorithm for solving their word problem.

A normal form for the free left distributive law, Int. J. Algebra Comput. 4-4 (1994) 499-528, pdf file

(AMS: 20N02) We construct a new normal form for one variable terms up to left distributivity. The proof that this normal form exists for every term is considerably simpler than the corresponding proof for the forms previously introduced by Richard Laver. In particular the determination of the present normal form can be made in a primitive recursive way.

The naming problem for left distributivity, Lect. Notes Comp. Sci. 677 (1993) 57-78

(AMS: 20N02) We consider the problem of naming the variables of a term so that it becomes equivalent to a given term when left distributivity is assumed, and describe an algorithm for solving this question using conjugacy in a free group. The correctness of the algorithm is reduced to a conjecture involving some particular words. A skew version of the conjecture is established.

Braid groups and left distributive operations, Trans. Amer. Math. Soc., 345-1 (1994) 115-151, pdf file

(AMS: 20F36, 17A30, 17A50) The decidability of the word problem for the free left distributive law is proved by introducing a structure group which describes the underlying identities. This group is closely connected with Artin's braid group $\Bi$. Braid colourings associated with free left distributive structures are used to show the existence of a unique ordering on the braids which is compatible with left translation and such that every generator sigma_i is preponderant over all sigma_k with k smaller than i. This ordering is a linear ordering.

Deux propriétés des groupes de tresses, C. R. Acad. Sci. Paris 315 (1992) 633-638, fichier pdf
Preuve de la conjecture d'irréflexivité pour les structures distributives libres, C. R. Acad. Sci. Paris 314 (1992) 333-336
A canonical ordering for free LD systems, Proc. Amer. Math. Soc. 122-1 (1994) 31-37

About the irreflexivity hypothesis for LD-magmas, Lect. Notes in Logic 2 (1993) 46-61

Structural monoids associated to equational varieties, Proc. Amer. Math. Soc. 117-2 (1993) 293-304
Problème de mots dans les gerbes libres, Theor. Comp. Sci. 94 (1992) 199-213
The adjoint representation of a left distributive magma, Comm. in Algebra 20-4 (1992) 1201-1215
A criterion for proving noetherianity of a relation, Theor. Comp. Sci. 93-2 (1992) 321-326
An alternative proof of Laver's result on the algebra generated by an elementary embedding, MSRI Pub. 26, Springer (1992) 27-33
Sur la structure des gerbes libres, C. R. Acad. Sci. Paris 309 (1989) 143-148
Free distributive groupoids, J. Pure Appl. Algebra 61 (1989) 123-146
Algebraic properties of the shift mapping, Proc. Amer. Math. Soc. 106-3 (1989) 617-623
A coding of the countable orderings, Studia Logica 49-4 (1990) 585-590
Pi11-complete families of elementary sequences, Ann. P. Appl. Logic 38 (1988) 257-287
Infinite products in monoids, Semigroup Forum 34 (1986) 21-68
Turing complexity of the ordinals, Inform. Proc. Letters 13 (1986) 167-170
Une propriété de cloture de l'ensemble des images d'une mesure, C. R. Acad. Sci. Paris 229 (1984) 803-806
An application of iterated ultrapowers, J. Symb. Logic 48-2 (1983) 225-235
Opérateurs différentiels et courbes elliptiques, Compositio Math 43 (1981) 71-99
Iterated ultrapowers and Prikry forcing, Ann. Math. Logic 15 (1978) 109-160
Intersections d'ultrapuissances, C. R. Acad. Sci. Paris 282 (1976) 935-938
Solution d'une conjecture de Bukovsky, C. R. Acad. Sci. Paris 281 (1975) 821-824