Critical exponents of infinite balanced words

Rampersad, Narad; Shallit, Jeffrey; Vandomme, Elise

doi:10.1016/j.tcs.2018.10.017

Request a copy

Article (Scientific journals)

Critical exponents of infinite balanced words

Rampersad, Narad; Shallit, Jeffrey; Vandomme, Elise

2018 • In Theoretical Computer Science, In press

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/231718

DOI
10.1016/j.tcs.2018.10.017

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Rampersad_Shallit_Vandomme_critical_exponent_preprint.pdf

Author preprint (325.24 kB)

Request a copy

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Infinite word; Balanced word; Sturmian word; Critical exponent

Abstract :

[en] Over an alphabet of size 3 we construct an infinite balanced word with critical exponent 2+\sqr{2}/2 . Over an alphabet of size 4 we construct an infinite balanced word with critical exponent (5+\sqr{5})/4. Over larger alphabets, we give some candidates for balanced words (found computationally) having small critical exponents. We also explore a method for proving these results using the automated theorem prover Walnut.

Disciplines :

Mathematics

Author, co-author :

Rampersad, Narad; University of Winnipeg

Shallit, Jeffrey; University of Waterloo > School of Computer Science

Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Probabilités et statistique mathématique

Language :

English

Title :

Critical exponents of infinite balanced words

Publication date :

2018

Journal title :

Theoretical Computer Science

ISSN :

0304-3975

Publisher :

Elsevier, Netherlands

Volume :

In press

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.sciencedirect.com/science/article/pii/S0304397518306388

Available on ORBi :

since 17 January 2019

Statistics

Number of views

45 (7 by ULiège)

Number of downloads

1 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Allouche, J.-P., Shallit, J., Automatic Sequences. 2003, Cambridge University Press, Cambridge.
Berstel, J., Séébold, P., Sturmian words. Chapter 2 Lothaire, M., (eds.) Algebraic Combinatorics on Words Encyclopedia Math. Appl., vol. 30, 2002, Cambridge University Press, Cambridge, 45–110.
Currie, J., Saari, K., Least periods of factors of infinite words. Theor. Inform. Appl. 43 (2009), 165–178.
Damanik, D., Lenz, D., The index of Sturmian sequences. European J. Combin. 23 (2002), 23–29.
de Luca, A., Combinatorics of standard Sturmian words. Structures in Logic and Computer Science LNCS, vol. 1261, 1997, Springer, 249–267.
Du, C.F., Mousavi, H., Schaeffer, L., Shallit, J., Decision algorithms for Fibonacci-automatic words, III: enumeration and Abelian properties. Internat. J. Found. Comput. Sci. 27 (2016), 943–963.
Furstenberg, H., Poincaré recurrence and number theory. Bull. Amer. Math. Soc. 5 (1981), 211–234.
Goulden, I., Granville, A., Richmond, B., Shallit, J., Natural exact covering systems and the reversion of the Möbius series. Preprint arXiv:1711.04109, 2017.
Graham, R.L., Covering the positive integers by disjoint sets of the form {[nα+β]:n=1,2,…}. J. Combin. Theory Ser. A 15 (1973), 354–358.
Hieronymi, P., Terry, A., Ostrowski numeration systems, addition and finite automata. Notre Dame J. Form. Log. 59 (2018), 215–232.
Hubert, P., Suites équilibrées. Theoret. Comput. Sci. 242 (2000), 91–108.
Justin, J., Pirillo, G., Fractional powers in Sturmian words. Theoret. Comput. Sci. 255 (2001), 363–376.
Lenstra, H.W. Jr., Shallit, J., Continued fractions and linear recurrences. Math. Comp. 61 (1993), 351–354.
Lothaire, M., Algebraic Combinatorics on Words. 2002, Cambridge University Press.
Mignosi, F., Pirillo, G., Repetitions in the Fibonacci infinite word. RAIRO Theor. Inform. Appl. 26 (1992), 199–204.
Mignosi, F., Restivo, A., Salemi, S., Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998), 153–167.
Mousavi, H., Automatic theorem proving in Walnut. Preprint arXiv:1603.06017, 2016.
Mousavi, H., Schaeffer, L., Shallit, J., Decision algorithms for Fibonacci-automatic words, I: basic results. RAIRO Theor. Inform. Appl. 50 (2016), 39–66.
Ostrowski, A., Bemerkungen zur Theorie der diophantischen Approximationen. Hambg. Abh. 1 (1922), 77–98 in German.
Peltomäki, J., Characterization of repetitions in Sturmian words: a new proof. Inform. Process. Lett. 115 (2015), 886–891.
Peltomäki, J., Privileged Words and Sturmian Words. PhD thesis, TUCS Dissertations No. 214, August 2016 available at http://www.utupub.fi/handle/10024/124473.
Pirillo, G., Fibonacci numbers and words. Discrete Math. 173 (1997), 197–207.
Tijdeman, R., Zamboni, L., Fine and Wilf words for any periods. Indag. Math. 14 (2003), 135–147.
Tijdeman, R., Zamboni, L., Fine and Wilf words for any periods II. Theoret. Comput. Sci. 410 (2009), 3027–3034.
Vuillon, L., Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 787–805.