Matching patterns with variables under edit distance
From MaRDI portal
Publication:6111591
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
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