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

A

This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.

*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.

Tags: 최일규