Generating random braids

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jan 2013Embargo end date: 01 Dec 2011 Spain English Publisher:Elsevier BVJournal:Journal of Combinatorial Theory, Series A, volume 120, pages 111-128 (issn: 0097-3165,

Copyright policy )Funded by:ARC | Algorithmic approaches to...

Authors: Volker Gebhardt; Juan González-Meneses;

doi: 10.1016/j.jcta.2012.07.003 , 10.48550/arxiv.1112.5485

arXiv: 1112.5485

handle: 11441/42263

Generating random braids

- Summary
- Subjects
- Metrics

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.

Country

Spain

Related Organizations

University of Seville
Spain
Western Sydney University
Australia

Keywords

Uniform random generator, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), random braids, Random braids, Lexicographically minimal representatives, Group Theory (math.GR), regular language, Theoretical Computer Science, 20F36 (Primary) 20F10, 05A15, 68W20, 68R05 (Secondary), XXXXXX - Unknown, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, forbidden prefixes, Regular language, Computational Theory and Mathematics, Finite state automata, Combinatorics (math.CO), finite state automata, Forbidden prefixes, Mathematics - Group Theory, Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average