On the parameterised complexity of string morphism problems

DOI10.4230/LIPICS.FSTTCS.2013.55MaRDI QIDQ2963897zbMATH OpenFDO

Authors Henning Fernau, Markus L. Schmid, Yngve Villanger

Publication date 21 February 2017

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)

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

Cited in

(7)

• scientific article; zbMATH DE number 6851884 (Why is no real title available?)
• On the parameterised complexity of string morphism problems
• Document spanners: from expressive power to decision problems
• Closure properties of pattern languages
• The invariant problem for binary string structures and the parallel complexity theory of queries
• Variant Satisfiability of Parameterized Strings
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)

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)