String editing under pattern constraints

DOI10.1016/J.TCS.2024.114889MaRDI QIDQ6646447zbMATH OpenFDO

Authors Robert D. Barish, Tetsuo Shibuya

Publication date 2 December 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114889

zbMATH Keywords

combinatorial pattern matchingcombinatorics on wordsfixed-parameter tractabilitylanguage edit distanceparameterized complexityregular expressionsstring editing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Mathematical Theory of Communication
• A Minimum Distance Error-Correcting Parser for Context-Free Languages
• A note on two problems in connexion with graphs
• A simple algorithm for the constrained sequence problems
• A Space-Economical Suffix Tree Construction Algorithm
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• An efficient context-free parsing algorithm
• Approximate matching of regular expressions
• Approximate regular expression pattern matching with concave gap penalties
• Approximately matching context-free languages
• Computing small partial coverings
• Constrained LCS: Hardness and Approximation
• Correcting Counter-Automaton-Recognizable Languages
• Efficient string matching
• Error detecting and error correcting codes
• Generalized String Matching
• scientific article; zbMATH DE number 3949728 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1026591 (Why is no real title available?)
• scientific article; zbMATH DE number 1952745 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• scientific article; zbMATH DE number 7651098 (Why is no real title available?)
• Linear approximation of shortest superstrings
• Local search for string problems: brute-force is essentially optimal
• New efficient algorithms for the LCS and constrained LCS problems
• Node-and edge-deletion NP-complete problems
• On finding minimal length superstrings
• On the generalized constrained longest common subsequence problems
• Optimization, approximation, and complexity classes
• Optimizing restriction site placement for synthetic genomes
• Polynomial Codes Over Certain Finite Fields
• Programming Techniques: Regular expression search algorithm
• Quadratic-time algorithm for a string constrained LCS problem
• Syntax-directed least-errors analysis for context-free languages
• The approximation of maximum subgraph problems
• The constrained longest common subsequence problem
• The node-deletion problem for hereditary properties is NP-complete
• The String-to-String Correction Problem
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time

This page was built for publication: String editing under pattern constraints

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