Back to Search
Start Over
On the Parameterised Complexity of String Morphism Problems
- Publication Year :
- 2013
-
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.
Details
- Database :
- OAIster
- Notes :
- application/pdf, English
- Publication Type :
- Electronic Resource
- Accession number :
- edsoai.ocn868121900
- Document Type :
- Electronic Resource
- Full Text :
- https://doi.org/10.4230.LIPIcs.FSTTCS.2013.55