On the parameterised complexity of string morphism problems

DOI10.4230/LIPICS.FSTTCS.2013.55zbMATH Open1359.68128MaRDI QIDQ2963897FDOQ2963897

Authors: Henning Fernau, Markus L. Schmid, Yngve Villanger 

Publication date: 21 February 2017

Recommendations

• On the parameterised complexity of string morphism problems
• Algorithms for detecting morphic images of a word
• Multivariate algorithmics for NP-hard string problems
• Developments in Language Theory
• Unambiguous erasing morphisms in free monoids

zbMATH Keywords

exponential time hypothesisstring morphismsparameterised complexitypattern languagesstring problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Cited In (9)

• Parameterized complexity of discrete Morse theory
• A parameterized study of maximum generalized pattern matching problems
• Title not available (Why is that?)
• On the parameterised complexity of string morphism problems
• Document spanners: from expressive power to decision problems
• Closure properties of pattern languages
• Variant Satisfiability of Parameterized Strings
• Title not available (Why is that?)
• The invariant problem for binary string structures and the parallel complexity theory of queries

This page was built for publication: On the parameterised complexity of string morphism problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963897)