Polynomial versus Exponential Growth in Repetition-Free Binary Words

Simple item page
dc.creatorKarhumaki, Juhani
dc.creatorShallit, Jeffrey
dc.date2003-04-07
dc.date.accessioned2026-07-07T04:56:41Z
dc.date.available2026-07-07T04:56:41Z
dc.descriptionIt 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.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/math/0304095
dc.identifierhttp://arxiv.org/abs/math/0304095
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/67012
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subject68R15
dc.titlePolynomial versus Exponential Growth in Repetition-Free Binary Words
dc.typetext

Files

Collections

arXiv