Generating random braids

Gebhardt, Volker; González-Meneses López, Juan

doi:10.1016/j.jcta.2012.07.003

Artículo

dc.creator	Gebhardt, Volker	es
dc.creator	González-Meneses López, Juan	es
dc.date.accessioned	2016-06-15T07:08:25Z
dc.date.available	2016-06-15T07:08:25Z
dc.date.issued	2013-01
dc.identifier.citation	Gebhardt, V. y González-Meneses López, J. (2013). Generating random braids. Journal of Combinatorial Theory, Series A, 120 (1), 111-128.
dc.identifier.issn	0097-3165	es
dc.identifier.issn	1096-0899	es
dc.identifier.uri	http://hdl.handle.net/11441/42263
dc.description.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.	es
dc.description.sponsorship	Australian Research Council’s Discovery Projects	es
dc.description.sponsorship	Ministerio de Ciencia e Innovación	es
dc.description.sponsorship	Junta de Andalucía	es
dc.description.sponsorship	Fondo Europeo de Desarrollo Regional	es
dc.format	application/pdf	es
dc.language.iso	eng	es
dc.publisher	Elsevier	es
dc.relation.ispartof	Journal of Combinatorial Theory, Series A, 120 (1), 111-128.
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 Internacional	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/	*
dc.subject	Random braids	es
dc.subject	Uniform random generator	es
dc.subject	Lexicographically minimal representatives	es
dc.subject	Regular language	es
dc.subject	Forbidden prefixes	es
dc.subject	Finite state automata	es
dc.title	Generating random braids	es
dc.type	info:eu-repo/semantics/article	es
dcterms.identifier	https://ror.org/03yxnpp24
dc.type.version	info:eu-repo/semantics/submittedVersion	es
dc.rights.accessRights	info:eu-repo/semantics/openAccess	es
dc.contributor.affiliation	Universidad de Sevilla. Departamento de álgebra	es
dc.relation.projectID	DP1094072	es
dc.relation.projectID	MTM2010- 19355	es
dc.relation.projectID	P09-FQM-5112	es
dc.relation.publisherversion	http://dx.doi.org/10.1016/j.jcta.2012.07.003
dc.identifier.doi	10.1016/j.jcta.2012.07.003	es
idus.format.extent	23 p.	es
dc.journaltitle	Journal of Combinatorial Theory, Series A	es
dc.publication.volumen	120	es
dc.publication.issue	1	es
dc.publication.initialPage	111	es
dc.publication.endPage	128	es
dc.relation.publicationplace	Amsterdam	es
dc.identifier.idus	https://idus.us.es/xmlui/handle/11441/42263

Ficheros	Tamaño	Formato	Ver	Descripción
Generating random braids.pdf	317.9Kb	[PDF]	Ver/Abrir

Este registro aparece en las siguientes colecciones

Artículos (Álgebra)

Mostrar el registro sencillo del ítem

Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional