Normal forms of random braids.

DOI10.1016/J.JALGEBRA.2013.10.008MaRDI QIDQ402699zbMATH OpenOpenAlexFDO

Authors Volker Gebhardt, Stephen Tawn

Publication date 28 August 2014

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.6676

zbMATH Keywords

algorithmsgrowth ratesexpected valueGarside groupsregular languagesnormal form theoremsGarside monoidspenetration distancerandom braids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Braid groups; Artin groups (20F36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

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.

Recommendations

• Generating random braids
• Solving random equations in Garside groups using length functions.
• A fast algorithm to the conjugacy problem on generic braids.
• Boundaries of braid groups and the Markov-Ivanovsky normal form
• A GATHERING PROCESS IN ARTIN BRAID GROUPS

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1759777 (Why is no real title available?)
• An algebraic method for public-key cryptography
• Artin-Gruppen und Coxeter-Gruppen
• Automatic Structures for Torus Link Groups
• Combinatorial Complexity of Regular Languages
• Generating random braids
• Geodesic automation and growth functions for Artin groups of finite type
• Groupes de Garside
• Growth rates of complexity of power-free languages
• On the genericity of pseudo-Anosov braids. I: Rigid braids.
• THE BRAID GROUP AND OTHER GROUPS
• The Magma algebra system. I: The user language
• The dual braid monoid
• Theory of braids

Cited in

(10)

• Asymptotic combinatorics of Artin-Tits monoids and of some other monoids
• Solving random equations in Garside groups using length functions.
• Generating random braids
• Combinatorics of normal sequences of braids
• The Bressaud normal form of braids through word rewrite systems.
• On the penetration distance in Garside monoids
• A GATHERING PROCESS IN ARTIN BRAID GROUPS
• Uniform measures on braid monoids and dual braid monoids
• Boundaries of braid groups and the Markov-Ivanovsky normal form
• A Braided Version of Some Results of Skryabin

Describes a project that uses

Uses Software

• Magma

This page was built for publication: Normal forms of random braids.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402699)