• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Polynomial Versus Exponential Growth in Repetition-Free Binary Words

Juhani Karhumäki, Jeffrey Shallit, Polynomial Versus Exponential Growth in Repetition-Free Binary Words. Journal of Combinatorial Theory Series A 105, 335–347, 2004.

Abstract:

It is known that the number of overlap-free binary words of length n grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing line between polynomial and exponential growth is 7/3. More precisely, there are only polynomially many binary words of length n that avoid 7/3-powers, but there are exponentially many binary words of length n that avoid (7/3)+ -powers. This answers an open question of Kobayashi from 1986.

BibTeX entry:

@ARTICLE{jKaSh04a,
  title = {Polynomial Versus Exponential Growth in Repetition-Free Binary Words},
  author = {Karhumäki, Juhani and Shallit, Jeffrey},
  journal = {Journal of Combinatorial Theory Series A},
  volume = {105},
  pages = {335–347},
  year = {2004},
  keywords = {Repetition-free; Cubefree; Polynomial growth; Exponential growth; Fractional power },
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 3

Edit publication