Fast Nielsen-Thurston classification of braids.
The paper provides an algorithm to decide when a braid is either reducible, periodic or pseudo-Anosov. The result relies on many previous works which also involve algorithms; notoriously the work by \textit{J. González-Meneses} and \textit{B. Wiest} [Algebr. Geom. Topol. 11, No. 5, 2971-3010 (2011; Zbl 1252.20035)]. The main result is the algorithm given as follows: Theorem 1. Let \(n\) be a positive integer. There exists an algorithm which decides the Nielsen-Thurston type of any braid \(x\) with \(n\) strands and runs in time \(O(|x|^2)\). The explicit description of the algorithm, which is provided in 4 steps, is too technical to be described here. Nevertheless a main step of the algorithm relies in the following relevant result which is Theorem 12. There exists a constant \(C(n)\) (depending only on \(n\)) such that for any pseudo-Anosov \(n\)-strand braid \(x\in SSS(x)\), the following holds: \(x\) has a rigid conjugate if and only if \(s^{C(n).|x|}(x)\) is rigid. As pointed out by the author, the algorithm rests on a linear bound, which is not explicitly known. Therefore the main result is an existence result.
- Fast algorithmic Nielsen-Thurston classification of four-strand braids.
- Reducible braids and Garside theory.
- A family of pseudo-Anosov braids with large conjugacy invariant sets.
- Efficient algorithm for recognizing the Nielsen-Thurston type of a three-strand braid.
- On the genericity of pseudo-Anosov braids. II: Conjugations to rigid braids.
- On reducible braids and composite braids
- scientific article; zbMATH DE number 475334
- Split Braids
- A fast algorithm to the conjugacy problem on generic braids.
- Conjugacy in Garside groups. I: Cyclings, powers and rigidity.
- A fast solution to the conjugacy problem in the four-strand braid group.
- A Garside-theoretic approach to the reducibility problem in braid groups.
- A new approach to the conjugacy problem in Garside groups.
- A new approach to the word and conjugacy problems in the braid groups
- A primer on mapping class groups
- ALGORITHMS FOR POSITIVE BRAIDS
- BRAIDS AND THE NIELSEN-THURSTON CLASSIFICATION
- Conjugacy in Garside groups. I: Cyclings, powers and rigidity.
- Conjugacy in Garside groups. II: Structure of the ultra summit set.
- Conjugacy in Garside groups. III: Periodic braids.
- Dual Garside structure and reducibility of braids.
- Fast algorithmic Nielsen-Thurston classification of four-strand braids.
- Foundations of Garside theory
- Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
- Geodesic automation and growth functions for Artin groups of finite type
- Geometry of the complex of curves. II: Hierarchical structure
- Groupes de Garside
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 193437 (Why is no real title available?)
- scientific article; zbMATH DE number 475334 (Why is no real title available?)
- Linearly bounded conjugator property for mapping class groups
- On reduction curves and Garside properties of braids.
- Reducible braids and Garside theory.
- Small braids with large ultra summit set.
- Solving the conjugacy problem in Garside groups by cyclic sliding.
- THE BRAID GROUP AND OTHER GROUPS
- The cyclic sliding operation in Garside groups.
- The infimum, supremum, and geodesic length of a braid conjugacy class.
- Train-tracks for surface homeomorphisms
- A general approach to fast prototype the topology of braided structures
- Algorithmic aspects of branched coverings. III/V: Erasing maps, orbispaces, and the Birman exact sequence
- Garside theory and subsurfaces: some examples in braid groups
- Algorithmic aspects of branched coverings. II/V: Sphere bisets and decidability of Thurston equivalence
- A family of pseudo-Anosov braids with large conjugacy invariant sets.
- Fast algorithmic Nielsen-Thurston classification of four-strand braids.
- BRAIDS AND THE NIELSEN-THURSTON CLASSIFICATION
- Geometric approaches to braid groups and mapping class groups
- An effective algebraic detection of the Nielsen-Thurston classification of mapping classes
- Reducible braids and Garside theory.
- Uniformly polynomial-time classification of surface homeomorphisms
- Efficient algorithm for recognizing the Nielsen-Thurston type of a three-strand braid.
- About the effective classification of conjugacy classes of braids
This page was built for publication: Fast Nielsen-Thurston classification of braids.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453736)
