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

regular languagefinite state automatarandom braidsforbidden prefixeslexicographically minimal representativesuniform random generator

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) 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

(11)

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

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)