[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 :
Mathematics
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 :
English
Title :
Regular sequences and synchronized sequences in abstract numeration systems
Publication date :
March 2022
Journal title :
European Journal of Combinatorics
ISSN :
0195-6698
eISSN :
1095-9971
Publisher :
Elsevier, Atlanta, Georgia
Volume :
101
Pages :
103475
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Baranwal, Aseem R., Shallit, Jeffrey, Critical exponent of infinite balanced words via the Pell number system. Combinatorics on Words Lecture Notes in Comput. Sci., vol. 11682, 2019, Springer, Cham, 80–92.
Berstel, Jean, Reutenauer, Christophe, Noncommutative Rational Series with Applications Encyclopedia of Mathematics and its Applications, vol. 137, 2011, Cambridge University Press, Cambridge, xiv+248.
Bertand-Mathis, Anne, Comment écrire les nombres entiers dans une base qui n'est pas entière. Acta Math. Hungar. 54:3–4 (1989), 237–241.
Berthé, Valérie, Frougny, Christiane, Rigo, Michel, Sakarovitch, Jacques, The carry propagation of the successor function. Adv. Appl. Math., 120, 2020, 102062 55.
Bruyère, Véronique, Hansel, Georges, Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181:1 (1997), 17–43.
Bruyère, Véronique, Hansel, Georges, Michaux, Christian, Villemaire, Roger, Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1:2 (1994), 191–238 Journées Montoises (Mons, 1992).
Carpi, Arturo, Maggi, Cristiano, On synchronized sequences and their separators. Theor. Inform. Appl. 35:6 (2001), 513–524.
Charlier, Émilie, First-order logic and numeration systems. Sequences, Groups, and Number Theory Trends Math., 2018, Birkhäuser/Springer, Cham, 89–141.
Charlier, Émilie, Le Gonidec, Marion, Rigo, Michel, Representing real numbers in a generalized numeration system. J. Comput. System Sci. 77:4 (2011), 743–759.
Charlier, Émilie, Rampersad, Narad, Shallit, Jeffrey, Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23:5 (2012), 1035–1066.
Charlier, Émilie, Rigo, Michel, Steiner, Wolfgang, Abstract numeration systems on bounded languages and multiplication by a constant. Integers, 8, 2008, A35, 19.
Cobham, Alan, On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969), 186–192.
Cobham, Alan, Uniform tag sequences. Math. Syst. Theory 6 (1972), 164–192.
Dumont, Jean-Marie, Thomas, Alain, Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. 65:2 (1989), 153–169.
Frougny, Christiane, Sakarovitch, Jacques, Number representation and finite automata. Combinatorics, Automata and Number Theory Encyclopedia Math. Appl., vol. 135, 2010, Cambridge Univ. Press, Cambridge, 34–107.
Frougny, Christiane, Solomyak, Boris, On representation of integers in linear numeration systems. Ergodic Theory of ZD Actions (Warwick, 1993–1994) London Math. Soc. Lecture Note Ser., vol. 228, 1996, Cambridge Univ. Press, Cambridge, 345–368.
Lecomte, Pierre B.A., Rigo, Michel, Numeration systems on a regular language. Theory Comput. Syst. 34:1 (2001), 27–44.
Leroy, Julien, Rigo, Michel, Stipulanti, Manon, Counting the number of non-zero coefficients in rows of generalized pascal triangles. Discrete Math. 340:5 (2017), 862–881.
Lothaire, M., Algebraic Combinatorics on Words Encyclopedia of Mathematics and its Applications, vol. 90, 2002, Cambridge University Press, Cambridge.
Rigo, Michel, Generalization of automatic sequences for numeration systems on a regular language. Theoret. Comput. Sci. 244 (2000), 271–281.
Rigo, Michel, Numeration systems on a regular language: arithmetic operations, recognizability and formal power series. Theoret. Comput. Sci. 269:1–2 (2001), 469–498.
Rigo, Michel, Maes, Arnaud, More on generalized automatic sequences. J. Autom. Lang. Comb. 7:3 (2002), 351–376.
Salomaa, Arto, Soittola, Matti, Automata-Theoretic Aspects of Formal Power Series Texts and Monographs in Computer Science, 1978, Springer-Verlag, New York-Heidelberg.
Schützenberger, Marcel Paul, On the definition of a family of automata. Inf. Control 4 (1961), 245–270.
