Artículo
Generating random braids
Autor/es | Gebhardt, Volker
González-Meneses López, Juan |
Departamento | Universidad de Sevilla. Departamento de álgebra |
Fecha de publicación | 2013-01 |
Fecha de depósito | 2016-06-15 |
Publicado en |
|
Resumen | 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 ... 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. |
Identificador del proyecto | DP1094072
MTM2010- 19355 P09-FQM-5112 |
Cita | Gebhardt, V. y González-Meneses López, J. (2013). Generating random braids. Journal of Combinatorial Theory, Series A, 120 (1), 111-128. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Generating random braids.pdf | 317.9Kb | [PDF] | Ver/ | |