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.55
URN: urn:nbn:de:0030-drops-43619
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4361/
Go to the corresponding LIPIcs Volume Portal

Fernau, Henning ; Schmid, Markus L. ; Villanger, Yngve

On the Parameterised Complexity of String Morphism Problems

pdf-format:
2.pdf (0.5 MB)

Abstract

Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly
replacing the symbols in u by strings) constitutes an NP-complete
problem. For example, the target string w := baaba can be obtained from the source string u := aba, by replacing a and b in u by the strings ba and a, respectively. In this paper, we contribute to the recently started investigation of the computational complexity of the string morphism problem by studying it in the framework of parameterised complexity.

BibTeX - Entry

@InProceedings{fernau_et_al:LIPIcs:2013:4361,
  author =	{Henning Fernau and Markus L. Schmid and Yngve Villanger},
  title =	{{On the Parameterised Complexity of String Morphism Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{55--66},
  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/4361},
  URN =		{urn:nbn:de:0030-drops-43619},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.55},
  annote =	{Keywords: String Problems, String Morphisms, Parameterised Complexity, Exponential Time Hypothesis, Pattern Languages}
}

Keywords: String Problems, String Morphisms, Parameterised Complexity, Exponential Time Hypothesis, Pattern Languages
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