Composition Problems for Braids

Author Igor Potapov



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2013.175.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Igor Potapov

Cite AsGet BibTex

Igor Potapov. Composition Problems for Braids. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 175-187, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.FSTTCS.2013.175

Abstract

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.
Keywords
  • Braid group
  • automata
  • group alphabet
  • combinatorics on words
  • matrix semigroups
  • NP-hardness
  • decidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail