| dbo:abstract
|
- In mathematics and theoretical computer science, a k-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-k representations of the integers. The class of k-regular sequences generalizes the class of k-automatic sequences to alphabets of infinite size. (en)
- En théorie des nombres, en informatique théorique et en combinatoire des mots, une suite régulière ou plus précisément une suite k-régulière où k>1 est un entier, est une suite d'entiers qui est définie par des relations de dépendance linéaire de certaines de ses sous-suites. Les sous-suites sont celles dont les indices forment des progressions arithmétiques dont les raisons sont des puissances de k. La condition est que toutes ces sous-suites appartiennent à un espace vectoriel (ou un module) finiment engendré. Il apparaît qu'un nombre considérable de suites d'entiers figurent dans cette catégorie. De plus, les suites k-régulières qui ne prennent qu'un nombre fini de valeurs sont exactement les suites k-automatiques. La suite 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, . . . qui compte la somme des bits dans l'écriture binaire des entiers naturels est un prototype de suite 2-régulière. C'est la suite . Un autre exemple est la suite 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, . . . des exposants des plus hautes puissances de 2 divisant les entiers (appelée en anglais la « ruler function »). C'est la suite . Le concept de suite k-régulière a été introduit par Allouche et Shallit. Ils en présentent un développement détaillé dans leur livre. Le lien avec les séries rationnelles en variables non commutatives, déjà mentionné dans leur article, est aussi détaillé dans le chapitre 5 du livre . Une présentation synthétique est donnée dans le premier chapitre (section 1.6.2 : Regular sequences) du livre . (fr)
|
