Avoiding Large Squares in Partial Words
Ilkyoo Choi (최일규)
Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
2011/12/22 Thu 4PM-5PM
Given a fixed alphabet, a word of length n is an n-tuple with entries in the alphabet. A hole is a character outside the alphabet that is viewed as representing any letter of the alphabet. A partial word is a string where each character is a hole or belongs to the alphabet. Two partial words having the same length are compatible if they agree at each position where neither has a hole.
A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words.
This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.
A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words.
This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.