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 | |