دورية أكاديمية
Regular sequences and synchronized sequences in abstract numeration systems
| العنوان: | Regular sequences and synchronized sequences in abstract numeration systems |
|---|---|
| المؤلفون: | Charlier, Emilie, Cisternino, Célia, Stipulanti, Manon |
| المصدر: | European Journal of Combinatorics, 101, 103475 (2022-03) |
| بيانات النشر: | Elsevier, 2022. |
| سنة النشر: | 2022 |
| مصطلحات موضوعية: | abstract numeration systems, regular sequences, automatic sequences, synchronized sequences, recognizable formal series, enumeration, first-order logic, weighted automata, synchronized relations, Physical, chemical, mathematical & earth Sciences, Mathematics, Physique, chimie, mathématiques & sciences de la terre, Mathématiques |
| الوصف: | 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. |
| نوع الوثيقة: | journal article http://purl.org/coar/resource_type/c_6501Test article |
| اللغة: | English |
| العلاقة: | urn:issn:0195-6698; urn:issn:1095-9971 |
| DOI: | 10.1016/j.ejc.2021.103475 |
| الوصول الحر: | https://orbi.uliege.be/handle/2268/253862Test |
| حقوق: | open access http://purl.org/coar/access_right/c_abf2Test info:eu-repo/semantics/openAccess |
| رقم الانضمام: | edsorb.253862 |
| قاعدة البيانات: | ORBi |
| DOI: | 10.1016/j.ejc.2021.103475 |
|---|