Scattered Factor-Universality of Words

DOI10.1007/978-3-030-48516-0_2OpenAlexW3029668781MaRDI QIDQ5041246

Laura Barker, Florin Manea, Dirk Nowotka, Katharina Harwardt, Pamela Fleischmann

Publication date: 13 October 2022

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.04629

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On the Simon's congruence neighborhood of languages, Absent Subsequences in Words, Tropical representations and identities of the stylic monoid, Ranking and Unranking k-Subsequence Universal Words, Longest Common Subsequence with Gap Constraints, On Arch Factorization and Subword Universality for Words and Compressed Words, Subsequences in bounded ranges: matching and analysis problems, Existential Definability over the Subword Ordering, Simon's congruence pattern matching, Absent subsequences in words, Unnamed Item, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, On Simon's congruence closure of a string, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, On Simon's congruence closure of a string

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized Pascal triangle for binomial coefficients of words
• Another generalization of abelian equivalence: binomial complexity of infinite words
• Descriptional and computational complexity of finite automata -- a survey
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• Absoluteness of subword inequality is undecidable
• Rich, Sturmian, and trapezoidal words
• On the complexity of computations under varying sets of primitives
• On universal partial words
• Universal partial words over non-binary alphabets
• Subword histories and Parikh matrices
• Complexity of universality and related problems for partially ordered NFAs
• Languages ordered by the subword order
• \(k\)-spectra of weakly-\(c\)-balanced words
• Algorithms for subsequence combinatorics
• Connections between subwords and certain matrix mappings
• On the index of Simon's congruence for piecewise testability
• Algorithms on Strings
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The Complexity of Downward Closure Comparisons
• The Height of Piecewise-Testable Languages with Applications in Logical Complexity
• Computing the \(k\)-binomial complexity of the Thue-Morse word
• Episturmian words and some constructions of de Luca and Rauzy