ALGORITHMIC COMBINATORICS ON PARTIAL WORDS

DOI10.1142/S0129054112400473zbMath1266.68145MaRDI 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

algorithms; subword complexity; combinatorics on words; partial words; pattern avoidrance

Mathematics Subject Classification ID

68R15: Combinatorics on words

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

Related Items

Characterizing Additive Systems, Several extensions of the Parikh matrix \(L\)-morphism, Solutions to the multi-dimensional Prouhet-Tarry-Escott problem resulting from composition of balanced morphisms, Square-free 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, On the Language of Primitive Partial Words, Relationally Periodic Sequences and Subword Complexity

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