PDPatrick Dehornoy

Patrick Dehornoy

*This is an algorithmically generated author record based on publicly available information.

Patrick Dehornoy has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    A cancellativity criterion for presented monoids

    by Patrick Dehornoy

    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.

  • Open Access

    Garside combinatorics for Thompson's monoid $F^+$ and a hybrid with the braid monoid $B\_\infty^+$

    by Patrick Dehornoy, Emilie Tesson

    On the model of simple braids, defined to be the left divisors of Garside's elements $\Delta\_n$ in the monoid $B\_\infty^+$ , we investigate simple elements in Thompson's monoid $F^+$ and in a larger monoid $H^+$ that is a hybrid of $B\_\infty^+$ 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.

  • Open Access

    Some aspects of the SD-world

    by Patrick Dehornoy

    We survey a few of the many results now known about the self-distributivity law and selfdistributive structures, with a special emphasis on the associated word problems and the algorithms solving them in good cases.

  • Open Access

    The Braid Shelf

    by Patrick Dehornoy

    The braids of $B\_\infty$ can be equipped with a selfdistributive operation $\mathbin{\triangleright}$ enjoying a number of deep properties. This text is a survey of known properties and open questions involving this structure, its quotients, and its extensions.

  • Open Access

    Multifraction reduction II: Conjectures for Artin-Tits groups

    by Patrick Dehornoy

    Multifraction reduction is a new approach to the word problem for Artin-Tits groups and, more generally, for the enveloping group of a monoid in which any two elements admit a greatest common divisor. This approach is based on a rewrite system ("reduction") that extends free group reduction. In this paper, we show that assuming that reduction satisfies a weak form of convergence called semi-convergence is sufficient for solving the word problem for the enveloping group, and we connect semi-convergence with other conditions involving reduction. We conjecture that these properties are valid for all Artin-Tits monoids, and provide partial results and numerical evidence supporting such conjectures.

  • Open Access

    Multifraction reduction III: The case of interval monoids

    by Patrick Dehornoy, Friedrich Wehrung

    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 and 1606.08995), 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).

  • Open Access

    Multifraction reduction I: The 3-Ore case and Artin-Tits groups of type FC

    by Patrick Dehornoy

    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.

  • Open Access

    Multifraction reduction IV: Padding and Artin-Tits groups of sufficiently large type

    by Patrick Dehornoy, Derek F. Holt, Sarah Rees

    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 $\mathrm{H}$. As an application, we show that all Artin-Tits groups of sufficiently large type satisfy some weakening Conjecture $\mathrm{A^{padded}}$ of Conjecture $\mathrm{A}$, thus showing that the reduction approach is relevant for these groups.

  • Open Access

    Quadratic normalisation in monoids

    by Patrick Dehornoy, Yves Guiraud

    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 and 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.