2026-07-23T04:54:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4371 2024-03-06T10:34:58Z ddc:004 open_access

Composition Problems for Braids Potapov, Igor Braid group automata group alphabet combinatorics on words matrix semigroups NP-hardness decidability In this paper we investigate the decidability and complexity of problems related to braid composition. While all known problems for a class of braids with 3 strands, B_3, have polynomial time solutions we prove that a very natural question for braid composition, the membership problem, is NP-hard for braids with only 3 strands. The membership problem is decidable for B_3, but it becomes harder for a class of braids with more strands. In particular we show that fundamental problems about braid compositions are undecidable for braids with at least 5 strands, but decidability of these problems for B_4 remains open. The paper introduces a few challenging algorithmic problems about topological braids opening new connections between braid groups, combinatorics on words, complexity theory and provides solutions for some of these problems by application of several techniques from automata theory, matrix semigroups and algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Igor Potapov 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.175 urn:nbn:de:0030-drops-43711 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.175 eng https://creativecommons.org/licenses/by/3.0/legalcode