Enumeration and decidable properties of automatic sequences

Charlier, Emilie; Rampersad, Narad; Shallit, Jeffrey

doi:10.1142/S0129054112400448

Request a copy

Article (Scientific journals)

Enumeration and decidable properties of automatic sequences

Charlier, Emilie; Rampersad, Narad; Shallit, Jeffrey

2012 • In International Journal of Foundations of Computer Science, 23 (5), p. 1035-1066

Peer Reviewed verified by ORBi

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

DOI
10.1142/S0129054112400448

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

postprint.pdf

Author postprint (441.82 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 :

Automatic sequence; Regular sequence; enumeration; decidability

Abstract :

[en] We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; University of Waterloo > School of Computer Science

Rampersad, Narad

Shallit, Jeffrey

Language :

English

Title :

Enumeration and decidable properties of automatic sequences

Publication date :

2012

Journal title :

International Journal of Foundations of Computer Science

ISSN :

0129-0541

Publisher :

World Scientific Publishing Company

Volume :

Issue :

Pages :

1035-1066

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 19 June 2012

Statistics

Number of views

100 (23 by ULiège)

Number of downloads

6 (5 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Adamdzewski, B., Bugeaud, Y., Palindromic continued fractions (2007) Ann. Inst. Fourier 57, pp. 1557-1574
Allouche, J.-P., Baake, M., Cassaigne, J., Damanik, D., (2003) Palindrome Complexity. Theoret. Comput. Sci, 292, pp. 9-31
Allouche, J.-P., Rampersad, N., Shallit, J., Periodicity, repetitions, and orbits of an automatic sequence (2009) Theoret. Comput. Sci, 410, pp. 2795-2803
Allouche, J.-P., Shallit, J.O., The ring of k-regular sequences (1992) Theoret. Comput. Sci, 98, pp. 163-197
Allouche, J.-P., Shallit, J.O., The ring of k-regular sequences II (2003) Theoret. Comput. Sci, 307, pp. 3-29
Allouche, J.-P., Shallit, J., (2003) Automatic Sequences: Theory Applications General- Izations, , Cambridge University Press
Berstel, J., An exercise on Fibonacci representations (2001) RAIRO - Theoretical Informatics and Applications, 35 (6), pp. 491-498. , DOI 10.1051/ita:2001127
Berstel, J., Reutenauer, C., (2011) Noncommutative Rational Series with Applications 137 of Encyclopedia of Mathematics and Its Applications, , Cambridge University Press
Brown, S., Rampersad, N., Shallit, J., Vasiga, T., Squares and overlaps in the thue-morse sequence and some variants (2006) RAIRO - Theoretical Informatics and Applications, 40 (3), pp. 473-484. , http://www.edpsciences.org/articles/ita/pdf/2006/03/ita05024.pdf?access= ok, DOI 10.1051/ita:2006030, Word Avoidability, Complexity And Morphisms (WACAM)
Bruyere, V., Hansel, G., Bertrand numeration systems and recognizability (1997) Theoretical Computer Science, 181 (1), pp. 17-43. , PII S0304397596002605
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R., Logic and p-recognizable sets of integers (1994) Bull. Belgian Math. Soc, 1, pp. 191-238. , Corrigendum Bull Belg Math Soc 1 1994 577
Bucci, M., De Luca, A., Zamboni, L.Q., (2011) Reversible Christoffel Factorizations, , http://www.pdmi.ras.ru/EIMI/2011/RuFiDiM/booklet.pdf, Paper presented at the First Russian-Finnish Symposium on Discrete Mathematics St. Petersburg September 21-24 Abstract available at
Carpi, A., D'Alonzo, V., On the repetitivity index of infinite words (2009) Internat. J. Algebra Comput, 19, pp. 145-158
Carpi, A., D'Alonzo, V., On factors of synchronized sequences (2010) Theor. Comput. Sci, 411, pp. 3932-3937
Carpi, A., Maggi, C., On synchronized sequences and their separators (2001) RAIRO - Theoretical Informatics and Applications, 35 (6), pp. 513-524. , DOI 10.1051/ita:2001129
Cobham, A., Uniform tag sequences (1972) Math. Systems Theory, 6, pp. 164-192
Currie, J.D., Lexicographically least words in the orbit closure of the rudin-shapiro word (2011) Theor. Comput. Sci, 412, pp. 4742-4746
Currie, J.D., Saari, K., Least periods of factors of infinite words. RAIRO Inform (2009) Th'Eor. App, 43, pp. 165-178
Droste, M., Kuich, W., Vogler, H., (2009) Handbook of Weighted Automata, , Springer- Verlag
Fagnot, I., Sur les facteurs des mots automatiques (1997) Theoretical Computer Science, 172 (1-2), pp. 67-89
Frid, A., Infinite permutations vs. infinite words (2011) WORDS 2011, 8th International Conference 13-19 Elect Proc Theor Comput Sci, , http://arxiv.org/abs/1108.3616-1, P. Ambrož, S. Holub, and Z. Mas'akov'a, editors Available at
Frid, A., Zamboni, L.Q., On automatic infinite permutations RAIRO Inform. th'Eor. App. to Appear
Frougny, C., Solomyak, B., On representation of integers in linear numeration systems (1996) Ergodic Theory of Zd Actions, , In M. Pollicott and K. Schmidt, editors Warwick 1993-1994 228 of London Mathematical Society Lecture Note Series 345-368 Cambridge University Press
Garel, E., Séparateurs dans les mots infinis engendrés par morphismes (1997) Theoretical Computer Science, 180 (1-2), pp. 81-113. , PII S03043975960001090
Halava, V., Harju, T., K̈arki, T., Rigo, M., On the periodicity of morphic words (2010) Developments in Language Theory 2010 6224 of Lecture Notes in Computer Science, pp. 209-217. , Springer Verlag
Henshall, D., Shallit, J., Automatic theorem-proving in combinatorics on words (2012) Manuscript, , http://arxiv.org/abs/1203.3758, March 15 Available at
Honkala, J., A decision method for the recognizability of sets defined by number systems (1986) RAIRO Inform. th'Eor. App, 20, pp. 395-403
Klavzar, S., Milutinovic, U., Petr, C., Stern polynomials (2007) Advances in Applied Mathematics, 39 (1), pp. 86-95. , DOI 10.1016/j.aam.2006.01.003, PII S0196885806000807
Krieger, D., Shallit, J., Every real number greater than 1 is a critical exponent (2007) Theoretical Computer Science, 381 (1-3), pp. 177-182. , DOI 10.1016/j.tcs.2007.04.037, PII S0304397507003398
Kuich, W., Salomaa, A., (1986) Semirings Automata Languages, , Springer-Verlag
Leroux, J., A polynomial time Presburger criterion and synthesis for number decision diagrams (2005) 20th IEEE Symposium on Logic in Computer Science (LICS, 147-156. , IEEE Press 2005
Mignosi, F., Restivo, A., Characteristic Sturmian words are extremal for the critical factorization theorem Theoret. Comput. Sci., to Appear
Moss'E, B., Reconnaissabilit'e des substitutions et complexit'e des suites automatiques (1996) Bull. Soc. Math. France, 124, pp. 329-346
Nicolas, F., Pritykin, Yu., On uniformly recurrent morphic sequences (2009) Internat. J. Found. Comp. Sci, 20, pp. 919-940
Reznick, B., Some binary partition functions (1990) Analytic Number Theory 85 of Progr. Math, pp. 451-477. , Birkhäuser
Saari, K., (2008) On the Frequency and Periodicity of Infinite Words, , PhD Thesis University of Turku Finland
Sakarovitch, J., (2009) Elements of Automata Theory, , Cambridge University Press
Salomaa, A., Soittola, M., (1978) Automata-Theoretic Aspects of Formal Power Series, , Springer-Verlag
Scḧutzenberger, M.-P., On a theorem of R (1962) Jungen. Proc. Amer. Math. Soc, 13, pp. 885-890
Shallit, J., The critical exponent is computable for automatic sequences WORDS 2011, 8th International Conference, pp. 231-239. , http://arxiv.org/abs/1104.2303-2, Available at In P. Ambrož, S. Holub, and Z. Mas'akov'a, editors Elect Proc Theor Comput Sci 2011. Revised version, with L. Schaeffer, submitted
Widmer, S., Permutation Complexity of the Thue-Morse word (2011) Adv. in Appl Math, 47, pp. 309-329