Computing equality-free string factorisations

DOI10.1007/978-3-319-20028-6_32MaRDI QIDQ3195710zbMATH OpenOpenAlexFDO

Authors Markus L. Schmid

Publication date 20 October 2015

Published in Evolving Computability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-20028-6_32

zbMATH Keywords

FPTNP-hard string problemsstring factorisations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Computing equality-free and repetitive string factorisations
• The maximum equality-free string factorization problem: gaps vs. no gaps
• String factorisations with maximum or minimum dimension
• Generalized factorizations of words and their algorithmic properties
• Longest common abelian factors and large alphabets

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• Diverse Palindromic Factorization Is NP-complete
• Fast Pattern Matching in Strings
• Multivariate algorithmics for NP-hard string problems
• On the exact block cover problem
• Parametrized complexity theory.
• Pattern matching with variables: fast algorithms and new hardness results
• The Complexity of String Partitioning

Cited in

(10)

• String factorisations with maximum or minimum dimension
• scientific article; zbMATH DE number 6819809 (Why is no real title available?)
• Efficient parallel algorithms to test square-freeness and factorize strings
• scientific article; zbMATH DE number 7740932 (Why is no real title available?)
• Indeterminate string factorizations and degenerate text transformations
• The maximum equality-free string factorization problem: gaps vs. no gaps
• Enhanced string factoring from alphabet orderings
• Generic Algorithms for Factoring Strings
• Factorizing a String into Squares in Linear Time
• Computing equality-free and repetitive string factorisations

This page was built for publication: Computing equality-free string factorisations

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