ALGORITHMIC COMBINATORICS ON PARTIAL WORDS

DOI10.1142/S0129054112400473zbMath1266.68145OpenAlexW4297931929MaRDI QIDQ4923275

Francine Blanchet-Sadri

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054112400473

zbMATH Keywords

algorithmssubword complexitycombinatorics on wordspartial wordspattern avoidrance

Mathematics Subject Classification ID

Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

Several extensions of the Parikh matrix \(L\)-morphism, Characterizing Additive Systems, Relationally Periodic Sequences and Subword Complexity, Solutions to the multi-dimensional Prouhet-Tarry-Escott problem resulting from composition of balanced morphisms, Square-free partial words, On the Language of Primitive Partial Words, A generalization of Thue freeness for partial words, Overlap-freeness in infinite partial words, Testing avoidability on sets of partial words is hard, Efficient pattern matching in elastic-degenerate strings

Cites Work

• Constructing partial words with subword complexities not achievable by full words
• On minimal Sturmian partial words
• Avoiding Abelian squares in partial words
• Abelian repetitions in partial words
• Avoidable binary patterns in partial words
• Erratum to: ``Avoidable binary patterns in partial words
• A powerful abelian square-free substitution over 4 letters
• On abelian 2-avoidable binary patterns
• Avoidable patterns in strings of symbols
• Strongly non-repetitive sequences and progression-free sets
• Partial words and a theorem of Fine and Wilf
• Complexity of sequences and dynamical systems
• Rauzy's conjecture on billiards in the cube
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Complexity of Toeplitz sequences
• The subword complexity of a class of infinite binary words
• Long binary patterns are abelian 2-avoidable
• Avoiding Patterns in the Abelian Sense
• BLOCKING SETS OF TERMS
• Generalized String Matching
• Complexity of sequences defined by billiard in the cube
• Automatic Sequences
• Algorithmic Combinatorics on Partial Words