[en] We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively 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 a new characterization of the class of k-regular sequences. Many results extend to other sequences de ned 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