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
104 (23 by ULiège)
Number of downloads
6 (5 by ULiège)

Scopus citations®
 
53
Scopus citations®
without self-citations
27
OpenCitations
 
39
OpenAlex citations
 
76

publications
59
supporting
0
mentioning
14
contrasting
0
Smart Citations
59
0
14
0
Citing PublicationsSupportingMentioningContrasting
View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Bibliography


Similar publications



Contact ORBi