Reference : Enumeration and decidable properties of automatic sequences
Scientific congresses and symposiums : Paper published in a book
Physical, chemical, mathematical & earth Sciences : Mathematics
Enumeration and decidable properties of automatic sequences
Charlier, Emilie mailto [University of Waterloo > School of Computer Science > > >]
Rampersad, Narad [ > > ]
Shallit, Jeffrey [ > > ]
Actes de Numération 2011
Numération 2011
du 6 juin 2011 au 10 juin 2011
[en] Automatic sequence ; Decidability ; Enumeration ; Regular sequence
[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.

File(s) associated to this reference

Fulltext file(s):

Open access
Abstract-Numeration-2011.pdfAuthor preprint275.77 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
Numeration-Liege2011.pdfslides de la communication184.37 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.