Subsequences with generalised gap constraints: upper and lower complexity bounds
From MaRDI portal
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A partial k-arboretum of graphs with bounded treewidth
- Absoluteness of subword inequality is undecidable
- Algorithms for Computing the Longest Parameterized Common Subsequence
- An approach to software system modelling and analysis
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Behavior of digital sequences through exotic numeration systems
- Combinatorial algorithms for subsequence matching: a survey
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Connections between subwords and certain matrix mappings
- Consequences of Faster Alignment of Sequences
- Construction of Aho Corasick automaton in linear time for integer alphabets
- Crossing Numbers and Cutwidths
- Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints
- scientific article; zbMATH DE number 4049084 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 7297889 (Why is no real title available?)
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- Introduction to algorithms.
- Languages ordered by the subword order
- Longest Common Subsequence with Gap Constraints
- Matching patterns with variables under Simon's congruence
- Multivariate fine-grained complexity of longest common subsequence
- On Arch Factorization and Subword Universality for Words and Compressed Words
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- On the index of Simon's congruence for piecewise testability
- Pathwidth of outerplanar graphs
- Reducibility among combinatorial problems
- Searching subsequences
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- Software Descriptions with Flow Expressions
- String matching with variable length gaps
- Subsequences in bounded ranges: matching and analysis problems
- Subsequences with gap constraints: complexity bounds for matching and analysis problems
- Subword histories and Parikh matrices
- The complexity of downward closure comparisons
- The Complexity of Some Problems on Subsequences and Supersequences
- The complexity of theorem-proving procedures
- The height of piecewise-testable languages with applications in logical complexity
- The subtrace order and counting first-order logic
- The vertex separation and search number of a graph
- Tight hardness results for LCS and other sequence similarity measures
- Unshuffling a square is NP-hard
Cited in
(8)- Fast algorithms for window accumulated subsequence matching problem
- Tight bounds for the number of absent subsequences
- k-universality of regular languages revisited
- Subsequence matching and LCS with segment number constraints
- Longest common subsequence with gap constraints
- Generalized Parikh matrices for tracking subsequence occurrences
- NP-completeness on the length of double-arrays and the sparse matrix problem with at least logarithmic alphabets/widths
- Subsequence matching and analysis problems for formal languages
This page was built for publication: Subsequences with generalised gap constraints: upper and lower complexity bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891073)
