Composition problems for braids

DOI10.4230/LIPICS.FSTTCS.2013.175MaRDI QIDQ2963911zbMATH OpenOpenAlexFDO

Authors Igor Potapov

Publication date 21 February 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2013/4371/pdf/12.pdf

zbMATH Keywords

\(\mathrm {NP}\)-hardnessautomatabraid groupcombinatorics on wordsdecidabilitygroup alphabetmatrix semigroups

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Braid groups; Artin groups (20F36) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• The set of minimal braids is co-NP-complete
• About the effective classification of conjugacy classes of braids
• A new algorithm for solving the word problem in braid groups
• Polynomial braid combing
• Braids and Knots

Cited in

(10)

• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Weighted automata on infinite words in the context of attacker-defender games
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• Weighted automata on infinite words in the context of attacker-defender games
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• The word problem for braided monoidal categories is unknot-hard
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Membership problems in braid groups and Artin groups
• Reconstruction of braids

This page was built for publication: Composition problems for braids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963911)