Issue |
RAIRO-Theor. Inf. Appl.
Volume 47, Number 2, April-June 2013
|
|
---|---|---|
Page(s) | 195 - 199 | |
DOI | https://doi.org/10.1051/ita/2013033 | |
Published online | 25 April 2013 |
A note on constructing infinite binary words with polynomial subword complexity∗
1
Department of Computer Science, University of North
Carolina, PO Box
26170, Greensboro,
NC
27402–6170,
USA
blanchet@uncg.edu
2
Department of Mathematics, University of California,
San Diego, 9500 Gilman Drive, Dept
0112, LaJolla,
CA
92093–0112,
USA
3
School of Computer Science, Carnegie Mellon
University, 5000 Forbes
Avenue, Pittsburgh,
PA
15213–3891,
USA
Received: 18 May 2012
Accepted: 8 January 2013
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet { a,b } with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function is injective, we can obtain at most quadratic subword complexity, and if the gap function is blockwise injective, we can obtain at most cubic subword complexity. Here, we construct infinite binary words w such that pw(n) = Θ(nβ) for any real number β > 1.
Mathematics Subject Classification: 68R15
Key words: Binary words / subword complexity / gap function
This material is based upon work supported by the National Science Foundation under Grant No. DMS–1060775. We thank the referees of a preliminary version of this paper as well as Aleksandar Chakarov, Lucas Manuelli, Jarett Schwartz, and Slater Stich for their very valuable comments and suggestions.
© EDP Sciences 2013
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.