Absent Subsequences in Words
From MaRDI portal
Publication:6070611
DOI10.3233/fi-222159OpenAlexW3198339414MaRDI QIDQ6070611
Stefan Siemer, Maria Kosche, Tore Koß, Florin Manea
Publication date: 23 November 2023
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3233/fi-222159
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the leftmost critical factorization on unordered alphabet
- Automata and forbidden words
- Generalized Pascal triangle for binomial coefficients of words
- Bounded repairability of word languages
- Using minimal absent words to build phylogeny
- The pseudopalindromic completion of regular languages
- \(k\)-abelian pattern matching
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Descriptional and computational complexity of finite automata -- a survey
- The level ancestor problem simplified
- Patterns in permutations and words.
- A lower bound technique for the size of nondeterministic finite automata
- An algorithm for distinguishing efficiently bit-strings by their subsequences
- Absoluteness of subword inequality is undecidable
- Computing runs on a general alphabet
- Applications of generalized matrix searching to geometric algorithms
- Rich, Sturmian, and trapezoidal words
- On highly palindromic words
- Geometric applications of a matrix-searching algorithm
- A faster algorithm computing string edit distances
- Preserving order in a forest in less than logarithmic time and linear space
- On the complexity of computations under varying sets of primitives
- Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
- Words and forbidden factors
- On universal partial words
- Universal partial words over non-binary alphabets
- Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
- Reconstructing words from subwords in linear time
- Alignment-free sequence comparison using absent words
- Directed acyclic subsequence graph -- overview
- Log-logarithmic worst-case range queries are possible in space theta(N)
- How hard is computing the edit distance?
- Subword histories and Parikh matrices
- Complexity of universality and related problems for partially ordered NFAs
- Absent words in a sliding window with applications
- Languages ordered by the subword order
- The relative edit-distance between two input-driven languages
- \(k\)-spectra of weakly-\(c\)-balanced words
- Algorithms for subsequence combinatorics
- Connections between subwords and certain matrix mappings
- Word assembly through minimal forbidden words
- On the index of Simon's congruence for piecewise testability
- Searching subsequences
- Absent subsequences in words
- Efficient range searching for categorical and plain data
- Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
- Edit Distance for Pushdown Automata
- A linear space algorithm for computing maximal common subsequences
- The Complexity of Some Problems on Subsequences and Supersequences
- Order- n correction for regular languages
- The String-to-String Correction Problem
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- The Complexity of Downward Closure Comparisons
- Error Detecting and Error Correcting Codes
- Scattered Factor-Universality of Words
- Computing the Shortest String and the Edit-Distance for Parsing Expression Languages
- The Subtrace Order and Counting First-Order Logic
- Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
- The Height of Piecewise-Testable Languages with Applications in Logical Complexity
- Wavelet Trees Meet Suffix Trees
- Faster Longest Common Extension Queries in Strings over General Alphabets
- Algorithms on Strings
- THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Near-Optimal Range Reporting Structures for Categorical Data
- Existential length universality
- Minimal forbidden factors of circular words
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Episturmian words and some constructions of de Luca and Rauzy
- Watson-Crick palindromes in DNA computing
- On extended special factors of a word
