Reference : Enumeration and decidable properties of automatic sequences
Scientific congresses and symposiums : Paper published in a journal
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/125568
Enumeration and decidable properties of automatic sequences
English
Charlier, Emilie mailto [University of Waterloo > School of Computer Science > > >]
Rampersad, Narad [ > > ]
Shallit, Jeffrey [ > > ]
2011
Lecture Notes in Computer Science
6795
Developments in language theory
165-179
Yes
No
International
15th International Conference on Developments in Language Theory
du 19 juillet 2011 au 22 juillet 2011
Milan
Italy
[en] Automatic Sequence ; Regular sequence ; Decidability
[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 a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration
systems.
Researchers
http://hdl.handle.net/2268/125568

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
FINAL-SOUMISSION.pdfAuthor preprint254.02 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.