Article (Scientific journals)
Enumeration and decidable properties of automatic sequences
Charlier, Emilie; Rampersad, Narad; Shallit, Jeffrey
2012In International Journal of Foundations of Computer Science, 23 (5), p. 1035-1066
Peer Reviewed verified by ORBi
 

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



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 :
23
Issue :
5
Pages :
1035-1066
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 19 June 2012

Statistics


Number of views
78 (21 by ULiège)
Number of downloads
5 (5 by ULiège)

Scopus citations®
 
51
Scopus citations®
without self-citations
26
OpenCitations
 
39

Bibliography


Similar publications



Contact ORBi