Linear time subsequence and supersequence regex matching
From MaRDI portal
Cites work
- \(k\)-universality of regular languages
- A fast algorithm for computing longest common subsequences
- Absoluteness of subword inequality is undecidable
- Algorithms for the Longest Common Subsequence Problem
- Algorithms on Strings
- An approach to software system modelling and analysis
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Co-lexicographically ordering automata and regular languages. I
- Connections between subwords and certain matrix mappings
- Consequences of Faster Alignment of Sequences
- Directed acyclic subsequence graph -- overview
- Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints
- Document spanners: a formal approach to information extraction
- Efficiently testing Simon's congruence
- Finite automata for the sub- and superword closure of CFLs: descriptional and computational complexity
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 2051146 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- Languages ordered by the subword order
- On Arch Factorization and Subword Universality for Words and Compressed Words
- On the state complexity of scattered substrings and superstrings
- Programming Techniques: Regular expression search algorithm
- Quadratic conditional lower bounds for string problems and dynamic time warping
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- Software Descriptions with Flow Expressions
- Subcubic equivalences between path, matrix, and triangle problems
- Subsequence matching and analysis problems for formal languages
- Subword histories and Parikh matrices
- The complexity of downward closure comparisons
- The Complexity of Some Problems on Subsequences and Supersequences
- The edit distance to \(k\)-subsequence universality
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- The subtrace order and counting first-order logic
- Tight hardness results for LCS and other sequence similarity measures
- Unshuffling a square is NP-hard
- Which regular expression patterns are hard to match?
This page was built for publication: Linear time subsequence and supersequence regex matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310165)
