Article (Scientific journals)
Regular sequences and synchronized sequences in abstract numeration systems
Charlier, Emilie; Cisternino, Célia; Stipulanti, Manon
2022In European Journal of Combinatorics, 101, p. 103475
Peer Reviewed verified by ORBi


Full Text
Author preprint (687.13 kB)

All documents in ORBi are protected by a user license.

Send to


Keywords :
abstract numeration systems; regular sequences; automatic sequences; synchronized sequences; recognizable formal series; enumeration; first-order logic; weighted automata; synchronized relations
Abstract :
[en] The notion of b-regular sequences was generalized to abstract numeration systems by Maes and Rigo in 2002. Their definition is based on a notion of S-kernel that extends that of b-kernel. However, this definition does not allow us to generalize all of the many characterizations of b-regular sequences. In this paper, we present an alternative definition of S-kernel, and hence an alternative definition of S-regular sequences, which enables us to use recognizable formal series in order to generalize most (if not all) known characterizations of b-regular sequences to abstract numeration systems. We then give two characterizations of S-automatic sequences as particular S-regular sequences. Next, we present a general method to obtain various families of S-regular sequences by enumerating S-recognizable properties of S-automatic sequences. As an example of the many possible applications of this method, we show that, provided that addition is S-recognizable, the factor complexity of an S-automatic sequence defines an S-regular sequence. In the last part of the paper, we study S-synchronized sequences. Along the way, we prove that the formal series obtained as the composition of a synchronized relation and a recognizable series is recognizable. As a consequence, the composition of an S-synchronized sequence and a S-regular sequence is shown to be S-regular. All our results are presented in an arbitrary dimension d and for an arbitrary semiring K.
Disciplines :
Author, co-author :
Charlier, Emilie  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Cisternino, Célia ;  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 > Département de mathématique
Language :
Title :
Regular sequences and synchronized sequences in abstract numeration systems
Publication date :
March 2022
Journal title :
European Journal of Combinatorics
Publisher :
Elsevier, Atlanta, Georgia
Volume :
Pages :
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 10 December 2020


Number of views
79 (16 by ULiège)
Number of downloads
58 (5 by ULiège)

Scopus citations®
Scopus citations®
without self-citations


Similar publications

Contact ORBi