Generating random braids

DOI10.1016/J.JCTA.2012.07.003MaRDI QIDQ1758507zbMATH OpenOpenAlexWikidataFDO

Authors Volker Gebhardt, Juan González-Meneses

Publication date 9 November 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

finite state automataforbidden prefixeslexicographically minimal representativesrandom braidsregular languageuniform random generator

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Formal languages and automata (68Q45) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: We present an algorithm to generate positive braids of a given length as words in Artin generators with a uniform probability. The complexity of this algorithm is polynomial in the number of strands and in the length of the generated braids. As a byproduct, we describe a finite state automaton accepting the language of lexicographically minimal representatives of positive braids that has the minimal possible number of states, and we prove that its number of states is exponential in the number of strands.

Recommendations

• Normal forms of random braids.
• On lexicographic representatives in braid monoids
• ALGORITHMS FOR POSITIVE BRAIDS
• Every braid admits a short sigma-definite expression.
• A new algorithm for solving the word problem in braid groups

Cited in

(13)

• Rewrite systems for the positive braid semigroups
• Generating bracelets with fixed content
• Random walks on the BMW monoid: an algebraic approach
• On lexicographic representatives in braid monoids
• Randomly growing braid on three strands and the Manta Ray
• On the growth of Artin-Tits monoids and the partial theta function
• Generating bracelets in constant amortized time
• Generating fixed density bracelets of arbitrary base
• Normal forms of random braids.
• Uniform measures on braid monoids and dual braid monoids
• A GATHERING PROCESS IN ARTIN BRAID GROUPS
• The alternating normal form of braids and its minimal automaton
• Concatenating random matchings

This page was built for publication: Generating random braids

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