Searching for Zimin patterns

DOI10.1016/J.TCS.2015.01.004MaRDI QIDQ2512657zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter, Arseny M. Shur

Publication date 30 January 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Fibonacci wordonline algorithmunavoidable patternZimin word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Online algorithms; streaming algorithms (68W27)

Abstract: In the area of pattern avoidability the central role is played by special words called Zimin patterns. The symbols of these patterns are treated as variables and the rank of the pattern is its number of variables. Zimin type of a word $x$ is introduced here as the maximum rank of a Zimin pattern matching $x$. We show how to compute Zimin type of a word on-line in linear time. Consequently we get a quadratic time, linear-space algorithm for searching Zimin patterns in words. Then we how the Zimin type of the length $n$ prefix of the infinite Fibonacci word is related to the representation of $n$ in the Fibonacci numeration system. Using this relation, we prove that Zimin types of such prefixes and Zimin patterns inside them can be found in logarithmic time. Finally, we give some bounds on the function $f(n,k)$ such that every $k$-ary word of length at least $f(n,k)$ has a factor that matches the rank $n$ Zimin pattern.

Recommendations

• On long words avoiding Zimin patterns
• Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
• On Long Words Avoiding Zimin Patterns
• Tower-type bounds for unavoidable patterns in words
• Avoiding patterns in the abelian sense

Cites work

• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• Bounds on Zimin word avoidance
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Least Periods of Factors of Infinite Words
• Pattern avoidance: themes and variations
• Repetitions in the Fibonacci infinite word

Cited in

(3)

• The complexity of unavoidable word patterns
• On long words avoiding Zimin patterns
• Tower-type bounds for unavoidable patterns in words

This page was built for publication: Searching for Zimin patterns

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