Normal forms of random braids

Volker Gebhardt, Stephen Tawn

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)

    Abstract

    Analysing statistical properties of the normal forms of random braids, we observe that, except for an initial and a final region whose lengths are uniformly bounded (that is, the bound is independent of the length of the braid), the distributions of the factors of the normal form of sufficiently long random braids depend neither on the position in the normal form nor on the lengths of the random braids. Moreover, when multiplying a braid on the right, the expected number of factors in its normal form that are modified, called the expected penetration distance, is uniformly bounded. We explain these observations by analysing the growth rates of two regular languages associated to normal forms of elements of Garside groups, respectively to the modification of a normal form by right multiplication. A universal bound on the expected penetration distance in a Garside group yields in particular an algorithm for computing normal forms that has linear expected running time.
    Original languageEnglish
    Pages (from-to)115-137
    Number of pages23
    JournalJournal of Algebra
    Volume408
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Dive into the research topics of 'Normal forms of random braids'. Together they form a unique fingerprint.

    Cite this