Matching patterns with variables under edit distance

DOI10.1007/978-3-031-20643-6_20zbMath1525.68204arXiv2207.07477OpenAlexW4312560666MaRDI QIDQ6111591

Florin Manea, Stefan Siemer, Paweł Gawrychowski

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2207.07477

zbMATH Keywords

pattern matchingedit distancepattern with variables

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterised complexity of string morphism problems
• Extended regular expressions: succinctness and decidability
• Patterns with bounded treewidth
• Finding patterns common to a set of strings
• Document spanners: from expressive power to decision problems
• Approximate pattern matching on elastic-degenerate text
• Deterministic regular expressions with back-references
• A logic for document spanners
• Matching patterns with variables
• Pattern matching with variables: a multivariate complexity analysis
• A note on the complexity of matching patterns with variables
• Generalized function matching
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Revisiting Shinohara's algorithm for computing descriptive patterns
• Document Spanners
• Minimal Mutation Trees of Sequences
• Fast parallel and serial approximate string matching
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
• Pattern Matching with Variables
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Dynamic String Alignment.
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance