Reference : Enumeration and decidable properties of automatic sequences
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/125566
Enumeration and decidable properties of automatic sequences
English
Charlier, Emilie mailto [University of Waterloo > School of Computer Science > > >]
Rampersad, Narad [> >]
Shallit, Jeffrey [> >]
2012
International Journal of Foundations of Computer Science
World Scientific Publishing Company
23
5
1035-1066
Yes (verified by ORBi)
International
0129-0541
[en] Automatic sequence ; Regular sequence ; enumeration ; 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 some new characterizations
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/125566

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
postprint.pdfAuthor postprint431.46 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.