The complexity of unavoidable word patterns

DOI10.1007/S00224-022-10090-ZOpenAlexW4283361228MaRDI QIDQ2158299FDOQ2158299

Authors Paul Sauer 

Publication date 26 July 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

complexityavoidabilityword patternsunavoidable regularity

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Recommendations

• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Testing avoidability on sets of partial words is hard
• On the complexity of deciding avoidability of sets of partial words
• Unavoidable sets of partial words of uniform length
• scientific article; zbMATH DE number 1786461

Cites work

• scientific article; zbMATH DE number 3125709 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1786461 (Why is no real title available?)
• scientific article; zbMATH DE number 2188438 (Why is no real title available?)
• scientific article; zbMATH DE number 3246281 (Why is no real title available?)
• scientific article; zbMATH DE number 3296252 (Why is no real title available?)
• scientific article; zbMATH DE number 3297137 (Why is no real title available?)
• scientific article; zbMATH DE number 3375509 (Why is no real title available?)
• 2726. A problem on strings of beads
• Abelian squares are avoidable on 4 letters
• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• Bounds on Zimin word avoidance
• Embedding the Dual of Π m in the Lattice of Equational Classes of Commutative Semigroups
• Examples of varieties of semigroups
• INFINITE PERIODIC GROUPS. I
• Intervals in the lattice of varieties
• Nonrepetitive colorings of graphs
• On nonrepetitive sequences
• On repetitions of blocks in binary sequences
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Open Problems in Pattern Avoidance
• Searching for Zimin patterns
• Some unsolved problems
• Square-free and cube-free colorings of the ordinals
• Tower-type bounds for unavoidable patterns in words
• Unavoidable regularities and factor permutations of words
• Unending chess, symbolic dynamics and a problem in semi-groups

Cited in

(3)

• Effective designs based on individual word length patterns
• THE PREDICTABILITY OF LETTERS IN WRITTEN ENGLISH
• Generalized wordlength patterns and strength

This page was built for publication: The complexity of unavoidable word patterns

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