Master’s Thesis Presentation • Algorithms and Complexity — Powers and Anti-Powers in Binary Words

Samin Riasat, Master’s candidate
David R. Cheriton School of Computer Science

Fici et al. recently introduced the notion of anti-powers in the context of combinatorics on words. A power (also called tandem repeat) is a sequence of consecutive identical blocks. An anti-power is a sequence of consecutive distinct blocks of the same length. 

Fici et al. showed that the existence of powers or anti-powers is an unavoidable regularity for sufficiently long words. In this thesis we explore this notion further in the context of binary words and obtain new results.