2026-07-26T10:55:53Z https://drops.dagstuhl.de/oai

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

On the Parameterised Complexity of String Morphism Problems Fernau, Henning Schmid, Markus L. Villanger, Yngve String Problems String Morphisms Parameterised Complexity Exponential Time Hypothesis Pattern Languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Fernau and Markus L. Schmid and Yngve Villanger 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.55 urn:nbn:de:0030-drops-43619 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.55 eng https://creativecommons.org/licenses/by/3.0/legalcode