License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.175
URN: urn:nbn:de:0030-drops-43711
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4371/
Go to the corresponding LIPIcs Volume Portal

Potapov, Igor

Composition Problems for Braids

pdf-format:
12.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{potapov:LIPIcs:2013:4371,
  author =	{Igor Potapov},
  title =	{{Composition Problems for Braids}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{175--187},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4371},
  URN =		{urn:nbn:de:0030-drops-43711},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.175},
  annote =	{Keywords: Braid group, automata, group alphabet, combinatorics on words, matrix semigroups, NP-hardness, decidability}
}

Keywords: Braid group, automata, group alphabet, combinatorics on words, matrix semigroups, NP-hardness, decidability
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI