Avoidable binary patterns in partial words

DOI10.1007/S00236-010-0129-0MaRDI QIDQ766156zbMATH OpenOpenAlexFDO

Authors Robert Mercaş, Sean Simmons, Eric Weissenstein, F. Blanchet-Sadri

Publication date 23 March 2012

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-010-0129-0

zbMATH Keywords

avoidability indexbinary patternscombinatorics on wordspartial words

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15)

Review text

The classification of all binary patterns according to partial word avoidability is obtained in this very interesting paper. A new terminology on unavoidable patterns is introduced in order to include some undefined positions called holes. Using iterated morphisms, the construction of binary partial words with infinitely many holes avoiding certain patterns becomes possible. Then the authors prove that all binary patterns 2-avoidable in full words are also non-trivially 2-avoidable in partial words. Hence, the final result presents the characterization of all binary patterns in terms of avoidability in partial words.

Recommendations

• Avoidable binary patterns in partial words
• Pattern avoidance in partial words dense with holes
• Computing the partial word avoidability indices of binary patterns
• Unary Pattern Avoidance in Partial Words Dense with Holes
• Computing depths of patterns

Cites work

• A generalization of Thue freeness for partial words
• Algorithmic Combinatorics on Partial Words
• Avoidable binary patterns in partial words
• Avoidable patterns in strings of symbols
• Avoidable patterns on two letters
• BLOCKING SETS OF TERMS
• Every binary pattern of length six is avoidable on the two-letter alphabet
• Freeness of partial words
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Overlap-freeness in infinite partial words
• Unavoidable binary patterns

Cited in

(24)

• Every binary pattern of length six is avoidable on the two-letter alphabet
• Unavoidable binary patterns
• Characterization of some binary words with few squares
• On the aperiodic avoidability of binary patterns with variables and reversals
• Avoiding cross-bifix-free binary words
• Pattern avoidance in partial words over a ternary alphabet
• Computing the partial word avoidability indices of ternary patterns
• Binary patterns in binary cube-free words: avoidability and growth
• Computing depths of patterns
• Unary Pattern Avoidance in Partial Words Dense with Holes
• Classifying all avoidable sets of partial words of size two
• Avoidable binary patterns in partial words
• Strict bounds for pattern avoidance
• Computing the partial word avoidability indices of binary patterns
• Computing the partial word avoidability indices of ternary patterns
• BINARY PATTERNS IN BINARY WORDS
• Number of holes in unavoidable sets of partial words. I.
• Every binary pattern of length greater than 14 is abelian-2-avoidable
• Pattern avoidance in partial words dense with holes
• On Long Words Avoiding Zimin Patterns
• scientific article; zbMATH DE number 2087216 (Why is no real title available?)
• Algorithmic combinatorics on partial words
• Partial matchings and pattern avoidance
• Open problems on avoidable patterns in partial words

This page was built for publication: Avoidable binary patterns in partial words

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