Article (Scientific journals)
Revising regular sequences in light of rational base numeration systems
Rigo, Michel; Stipulanti, Manon
2022In Discrete Mathematics, 345, p. 112735
Peer Reviewed verified by ORBi
 

Files


Full Text
regular-resubmission.pdf
Author preprint (448.02 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Regular sequences; abstract numeration systems; rational base numeration systems; decorated linear trees; kernels; linear representations
Abstract :
[en] Regular sequences generalize the extensively studied automatic sequences. Let S be an abstract numeration system. When the numeration language L is prefix-closed and regular, a sequence is said to be S-regular if the module generated by its S-kernel is finitely generated. In this paper, we give a new characterization of such sequences in terms of the underlying numeration tree T(L) whose nodes are words of L. We may decorate these nodes by the sequence of interest following a breadth-first enumeration. For a prefix-closed regular language L, we prove that a sequence is S-regular if and only if the tree T(L) decorated by the sequence is linear, i.e., the decoration of a node depends linearly on the decorations of a fixed number of ancestors. Next, we introduce and study regular sequences in a rational base numeration system, whose numeration language is known to be highly non-regular. We motivate and discuss our definition that a sequence is p/q -regular if the underlying numeration tree decorated by the sequence is linear. We give the first few properties of such sequences, we provide a few examples of them, and we propose a method for guessing p/q-regularity. Then we discuss the relationship between p/q -automatic sequences and p/q -regular sequences. We finally present a graph-directed linear representation of a p/q-regular sequence. Our study permits us to highlight the places where the regularity of the numeration language plays a predominant role.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Stipulanti, Manon  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Revising regular sequences in light of rational base numeration systems
Publication date :
2022
Journal title :
Discrete Mathematics
ISSN :
0012-365X
eISSN :
1872-681X
Publisher :
Elsevier, Netherlands
Volume :
345
Pages :
112735
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
Available on ORBi :
since 18 January 2022

Statistics


Number of views
64 (6 by ULiège)
Number of downloads
32 (1 by ULiège)

Scopus citations®
 
0
Scopus citations®
without self-citations
0
OpenAlex citations
 
0

Bibliography


Similar publications



Contact ORBi