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

#### Files

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

All documents in ORBi are protected by a user license.

#### 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 [BE]
Available on ORBi :
since 18 January 2022

#### Statistics

Number of views
53 (6 by ULiège)
27 (1 by ULiège)

Scopus citations®

0
Scopus citations®
without self-citations
0

#### Bibliography

• Akiyama, S., Frougny, Ch., Sakarovitch, J., Powers of rationals modulo 1 and rational base number systems. Isr. J. Math. 168 (2008), 53–91.
• Allouche, J.-P., Shallit, J., The ring of k-regular sequences. Theor. Comput. Sci. 98 (1992), 163–197.
• Allouche, J.-P., Shallit, J., The ring of k-regular sequences II. Theor. Comput. Sci. 307 (2003), 3–29.
• Berstel, J., Reutenauer, C., Recognizable formal power series on trees. Theor. Comput. Sci. 18 (1982), 115–148.
• Berstel, J., Reutenauer, C., Noncommutative Rational Series with Applications. Encyclopedia of Math. and its Appl., vol. 137, 2010, Cambridge Univ. Press.
• Boore, G.C., Falconer, K.J., Attractors of directed graph IFSs that are not standard IFS attractors and their Hausdorff measure. Math. Proc. Camb. Philos. Soc. 54 (2013), 325–349.
• Charlier, É., Rampersad, N., Shallit, J., Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23 (2012), 1035–1066.
• Charlier, É., Cisternino, C., Stipulanti, M., Regular sequences and synchronized sequences in abstract numeration systems. Eur. J. Comb., 101, 2022, 103475.
• Lecomte, P., Rigo, M., Numeration systems on a regular language. Theory Comput. Syst. 34 (2001), 27–44.
• Leroy, J., Rigo, M., Stipulanti, M., Counting the number of non-zero coefficients in rows of generalized Pascal triangles. Discrete Math. 340 (2017), 862–881.
• Marsault, V., Énumération et numération. Doctoral thesis, 2015, Télecom-Paristech.
• Marsault, V., Sakarovitch, J., Breadth-first serialisation of trees and rational languages. Developments in Language Theory - 18th International Conference, Ekaterinburg, Russia, August 26–29, 2014 Lect. Notes Comp. Sci., vol. 8633, 2014, 252–259.
• Marsault, V., Sakarovitch, J., Trees and languages with periodic signature. Indag. Math. 28 (2017), 221–246.
• Rigo, M., Maes, A., More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002), 351–376.
• Rigo, M., Stipulanti, M., Automatic sequences: from rational bases to trees. preprint arXiv:2102.10828, 2021.
• Rowland, E., What is an automatic sequence?. Not. Am. Math. Soc. 62 (2015), 274–276.
• Rowland, E., IntegerSequences: a package for computing with k-regular sequence. https://ericrowland.github.io/packages.html.
• Rowland, E., Stipulanti, M., Avoiding 5/4-powers on the alphabet of nonnegative integers. Electron. J. Comb., 27, 2020, 3.42.
• Shallit, J., Remarks on inferring integer sequences. https://cs.uwaterloo.ca/~shallit/Talks/infer.ps.
• Sloane, N., et al. The on-line encyclopedia of integer sequences. http://oeis.org.