Generating random braids

Volker Gebhardt; Juan González-Meneses

doi:10.1016/j.jcta.2012.07.003

Generating random braids

Volker Gebhardt
, Juan González-Meneses

School of Computer, Data & Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

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.

Original language	English
Pages (from-to)	111-128
Number of pages	18
Journal	Journal of Combinatorial Theory, Series A
Volume	120
Issue number	1
DOIs	https://doi.org/10.1016/j.jcta.2012.07.003
Publication status	Published - 2013

Keywords

finite state automata
forbidden prefixes
random braids
regular language

Access to Document

10.1016/j.jcta.2012.07.003

Cite this

@article{a1ab384613844cbcae589472d6a0e0d2,

title = "Generating random braids",

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.",

keywords = "finite state automata, forbidden prefixes, random braids, regular language",

author = "Volker Gebhardt and Juan Gonz{\'a}lez-Meneses",

year = "2013",

doi = "10.1016/j.jcta.2012.07.003",

language = "English",

volume = "120",

pages = "111--128",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press",

number = "1",

}

TY - JOUR

T1 - Generating random braids

AU - Gebhardt, Volker

AU - González-Meneses, Juan

PY - 2013

Y1 - 2013

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

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

KW - finite state automata

KW - forbidden prefixes

KW - random braids

KW - regular language

UR - http://handle.uws.edu.au:8081/1959.7/524463

U2 - 10.1016/j.jcta.2012.07.003

DO - 10.1016/j.jcta.2012.07.003

M3 - Article

SN - 0097-3165

VL - 120

SP - 111

EP - 128

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

Generating random braids

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this