Opened Access Generating random braids

Show item statistics
Export to
Author: Gebhardt, Volker
González-Meneses López, Juan
Department: Universidad de Sevilla. Departamento de álgebra
Date: 2013-01
Published in: Journal of Combinatorial Theory, Series A, 120 (1), 111-128.
Document type: Article
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.
Cite: Gebhardt, V. y González-Meneses López, J. (2013). Generating random braids. Journal of Combinatorial Theory, Series A, 120 (1), 111-128.
Size: 317.9Kb
Format: PDF


DOI: 10.1016/j.jcta.2012.07.003

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)