Scattered factor universality -- a survey

DOI10.1007/978-3-032-28404-4_2MaRDI QIDQ7356284zbMATH OpenFDO

Authors Pamela Fleischmann

Publication date 23 September 2026

Full work available at URL https://doi.org/10.1007/978-3-032-28404-4_2

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence
• \(k\)-universality of regular languages
• k-universality of regular languages revisited
• Absent Subsequences in Words
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• Characterization of a word by its subwords
• Computing longest Lyndon subsequences and longest common Lyndon subsequences
• Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints
• Existential Definability over the Subword Ordering
• Finite size corrections relating to distributions of the length of longest increasing subsequences
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (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?)
• Jumbled scattered factors
• Languages ordered by the subword order
• Matching patterns with variables under Simon's congruence
• Multivariate fine-grained complexity of longest common subsequence
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• On Arch Factorization and Subword Universality for Words and Compressed Words
• On problems related to absent subsequences
• On Simon's congruence closure of a string
• On the index of Simon's congruence for piecewise testability
• On the Simon's congruence neighborhood of languages
• Reconstructing Words from Right-Bounded-Block Words
• Reconstructing words from subwords in linear time
• Scattered Factor-Universality of Words
• Searching subsequences
• Simon's congruence pattern matching
• 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 height of piecewise-testable languages with applications in logical complexity
• The String-to-String Correction Problem
• The subtrace order and counting first-order logic
• Tight bounds for the number of absent subsequences

This page was built for publication: Scattered factor universality -- a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7356284)