Revisiting regular sequences in light of rational base numeration systems

• Published in: Discrete mathematics 2022-03, Vol.345 (3), p.112735, Article 112735
• Main Authors: Rigo, Michel, Stipulanti, Manon
• Format: Article
• Language: English
• Subjects: Abstract numeration systems; Decorated linear trees; Kernels; Linear representations; Rational base numeration systems; Regular sequences
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2021.112735

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 pq-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 pq-regularity. Then we discuss the relationship between pq-automatic sequences and pq-regular sequences. We finally present a graph-directed linear representation of a pq-regular sequence. Our study permits us to highlight the places where the regularity of the numeration language plays a predominant role.