scientific article; zbMATH DE number 7800491
From MaRDI portal
arXiv2208.14722MaRDI QIDQ6190431
Maria Kosche, Stefan Siemer, Tore Koß, Florin Manea
Publication date: 6 February 2024
Full work available at URL: https://arxiv.org/abs/2208.14722
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- String matching with variable length gaps
- Another generalization of abelian equivalence: binomial complexity of infinite words
- An algorithm for distinguishing efficiently bit-strings by their subsequences
- Absoluteness of subword inequality is undecidable
- Simple deterministic wildcard matching
- Rich, Sturmian, and trapezoidal words
- Finding patterns common to a set of strings
- Which problems have strongly exponential complexity?
- Directed acyclic subsequence graph -- overview
- Subword histories and Parikh matrices
- Languages ordered by the subword order
- Connections between subwords and certain matrix mappings
- On the index of Simon's congruence for piecewise testability
- Unshuffling a square is NP-hard
- Searching subsequences
- Absent subsequences in words
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- The Complexity of Some Problems on Subsequences and Supersequences
- Software Descriptions with Flow Expressions
- An approach to software system modelling and analysis
- The Complexity of Downward Closure Comparisons
- Querying Regular Languages over Sliding Windows
- Scattered Factor-Universality of Words
- The Subtrace Order and Counting First-Order Logic
- Fine-Grained Complexity Theory (Tutorial)
- Consequences of Faster Alignment of Sequences
- The Height of Piecewise-Testable Languages with Applications in Logical Complexity
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Algorithms on Strings
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Episturmian words and some constructions of de Luca and Rauzy
- On the complexity of \(k\)-SAT
