Electronic Proceedings in Theoretical Computer Science (Aug 2011)

Fife's Theorem for (7/3)-Powers

  • Narad Rampersad,
  • Jeffrey Shallit,
  • Arseny Shur

DOI
https://doi.org/10.4204/EPTCS.63.25
Journal volume & issue
Vol. 63, no. Proc. WORDS 2011
pp. 189 – 198

Abstract

Read online

We prove a Fife-like characterization of the infinite binary (7/3)-power-free words, by giving a finite automaton of 15 states that encodes all such words. As a consequence, we characterize all such words that are 2-automatic.