THEMES DE RECHERCHE ACTUELS
Fonction de Collatz
Nous nous intéressons à la fameuse fonction de Collatz définie pour tout entier n positif par f(n)=n/2 si n est pair et f(n) = 3n+1 sinon. Cette fonction, bien que très simple à définir, est à l'origine de la célèbre conjecture de Collatz. Celle-ci postule qu'en appliquant la fonction de Collatz un nombre suffisant de fois à partir de n'importe quel entier, on atteint le nombre 1.
Cette conjecture difficile, étudiée par de nombreux mathématiciens depuis plusieurs décennies, reste aujourd'hui un problème ouvert. Nous ne cherchons pas ici à la résoudre mais nous avons voulu apporter un nouveau point de vue sur cette fonction en utilisant des outils d'informatique théorique pour la décrire : les automates.
Pour définir des fonctions entières avec des automates, il faut tout d'abord choisir une base pour coder les entiers en mots. On utilise les transducteurs, dont les transitions sont étiquetées par des paires de mots et qui acceptent les représentations dans la base choisie des paires (n,f(n)). Bien sûr, la fonction de Collatz, qui n'utilise que des opérations arithmétiques de base, a déjà été définie par des transducteurs. L'approche la plus naturelle est l'utilisation de la base 2 inverse. En effet, le bit de poids faible à gauche nous indique immédiatement si l'entier est pair ou impair. S'il est pair, la division par 2 s'effectue en effaçant le 0 à gauche et s'il est impair le transducteur calcule la multiplication par 3 plus 1. Néanmoins, lorsque l'on compose les transducteurs obtenus pour représenter f2 puis f3 et cetera, de nombreux cas apparaissent et les transducteurs s'avèrent difficile à dessiner. Aucune forme de régularité ne permet de définir directement, pour tout entier p, un transducteur acceptant fp.
Etant donné que pour tout entier impair n, l'entier 3n+1 est pair, on peut considérer l'accélération de la fonction de Collatz f' définie pour tout entier n positif par f'(n)=n/2 si n est pair et f'(n) = (3n+1)/2 sinon. Notre approche pour réaliser f' est alors d'effectuer la division par 2 en base 3 directe. L'état final indique si l'entrée correspond à un entier pair ou impair. Dans ce dernier cas, une fonction terminale permet de concaténer un bit à droite de la sortie pour calculer le numérateur 3n+1. Ce transducteur, lettre-à-lettre et déterministe en entrée, peut se composer de façon standard en effectuant un produit de synchronisation. La difficulté étant, bien sûr, dans le calcul de la fonction terminale. Ainsi, pour tout entier p, nous sommes capables de définir un transducteur réalisant f'p à partir du transducteur de la division par 2p en base 3 muni d'une fonction terminale.
Pour tout entier p, on propose une façon de dessiner le transducteur de la division par 2p en base 3 sous forme de cercle et de façon régulière. On donne également une définition récurrente de la fonction terminale qui nous permet d'obtenir un transducteur (infini) sous forme de cône, réalisant l'itération de la composition f'*. Il se compose de l'union (infinie) des transducteurs de la division par 2p en base 3 et de transitions allant du niveau p+1 au niveau p représentant la fonction terminale. L'existence d'un entier p tel que f'p(n) = 1 se traduit par l'existence d'un chemin menant du sommet initial du niveau p au sommet de niveau 0 étiqueté en entrée par la représentation en base 3 de l'entier n et en sortie par 1.
Article: Ces résultats ont été présentés en conférence (D. Caucal and C. Rispal, "On the powers of the Collatz function", Machines, Computations and Universality, To appear in Lecture Notes in Computer Science (2024)) où ils ont reçu le prix du meilleur article de la conférence et sont en cours de rédaction pour une version longue dans une édition spéciale de Acta Informatica.Reconnaissabilité par automates
La reconnaissabilité apporte une approche générale pour extraire des algèbres de Boole dans des familles de langages, comme par exemple celles de la hiérarchie de Chomsky, celles de la hiérarchie des langages indexés de Maslov, ou encore la famille des langages acceptés par les réseaux de Petri.
La reconnaissabilité a été définie par Eilenberg en 1967: une partie d'un monoïde est reconnue par morphisme inverse d'une partie d'un monoïde fini. Pour un monoïde donné, l'ensemble des parties reconnues forment une algèbre de Boole. Cette notion de reconnaissabilité a été étendue, notamment pour les termes, les graphes finis, les traces, les mots indexés par des ordres totaux.
La reconnaissabilité est ici considérée pour les automates, où un automate est un graphe (généralement infini) orienté et étiqueté par des lettres avec des sommets initiaux et des sommets finaux. On définit la reconnaissabilité par un automate H selon une famille F d'automates comme l'ensemble Rec(F,H) des langages acceptés par les automates de F qui s'appliquent morphiquement en H.
Si H est l'automate Boucles n'ayant qu'un seul état, qui est initial et final, et dont toute lettre étiquette une boucle, alors tout automate s'applique morphiquement en Boucles. Aussi, la famille Rec(F,Boucles) est l'ensemble des langages acceptés par les automates de F et qui n'est généralement pas une algèbre de Boole.
Pour obtenir des algèbres de Boole, on ajoute une condition, dite structurelle, sur les morphismes. Pour cela, on considère une famille R de relations binaires à laquelle on associe la famille F(R) des automates dont toute transition étiquetée est une relation de R.
On introduit la reconnaissabilité selon F(R) en restreignant les morphismes à être des relations de R, ce qui définit la sous-famille sRec(F,H) des langages acceptés par les automates de F qui s'appliquent morphiquement et structurellement en H.
La reconnaissabilité structurelle permet d'obtenir des algèbres de Boole pas seulement pour des automates à pile, ou à pile de piles, ... mais aussi en autorisant plusieurs piles. Précisément et pour tous entiers positifs m et n, on définit l'ensemble P(m,n) des relations binaires suffixes définissables par m piles de n niveaux de pile de piles. Pour tout automate non ambigü H de F(P(m,n)), la famille sRec(F(P(m,n),H) est une algèbre de Boole vis à vis du langage L(H) accepté par H (le langage L(H) - M est dans la famille lorsque M l'est). Ce résultat reste vrai si on restreint P(m,n) à la famille C(m,n) des relations suffixes sur m compteurs de niveau n. En particulier, C(m,1) correspond aux systèmes d'addition de vecteurs de dimension m. On obtient aussi des algèbres de Boole relativement à la famille des langages contextuels.
Cette reconnaissabilité structurelle est générale mais elle ne permet pas d'obtenir la famille des langages algébriques visibles (ou input-driven)..
Article: "Recognizability for automata" avec Didier Caucal, 22ième DLT (Developments in Language Theory), publication LNCS 11088, Springer, M. Hoshi, S. Seki (Eds.), 206-218 (2018).
Algèbres de Boole par reconnaissabilité par longueur
On vient d'indiquer que la reconnaissabilité structurelle ne permet pas d'obtenir l'algèbre de Boole des langages algébriques visibles. Une autre façon de reconnaïtre des algèbres de Boole est de se restreindre aux morphismes déterministes qui préservent la longueur. Pour cela, on ne considère que des automates dont les sommets sont des mots. Pour F une famille d'automates et H un automate de F, on définit la famille lRec(F,H) des langages acceptés par les automates de F qui s'appliquent en H par morphisme préservant la longueur. Pour la famille F des automates à pile et pour H non ambigü , lRec(F,H) est une algèbre de Boole (selon le langage L(H) accepté par H). Par contre, on n'a plus de fermeture par complémentaire pour la famille des automates à pile de piles pour des automates H déterministes. Au lieu de restreindre les familles F aux automates déterministes, on demande en plus aux morphismes d'être déterministes. Précisément, un morphisme f appliqué à un automate G est déterministe si on n'a pas deux sommets initiaux de G de même image par f, et si les buts de deux arcs de G de même source et de même étiquette n'ont pas la même image par f. On considère alors la sous-famille dlRec(F,H) des langages des automates G de F pour lesquels il existe un morphisme de G dans H qui soit à la fois déterministe et qui préserve la longueur des sommets.
On obtient que toute famille dlRec(F,H) est une algèbre de Boole (selon L(H)) sous deux hypothèses. La première hypothèse est que l'automate H soit non ambigü et longueur-déterministe: deux sommets initiaux ne sont pas de même longueur, et deux buts d'arcs de même source et étiquette sont de longueur différente. La deuxième hypothèse est que la famille F soit fermée par deux opérations habituelles pour les automates finis. On a le produit de synchronisation par longueur donnant la fermeture par intersection de dlRec(F,H). Pour la fermeture par complémentaire: L(H) - L(G), on a une opération de superposition par longueur de G sur H. Les algèbres de Boole dlRec(F,H) sont alors obtenues pour la famille F des automates à pile qui est fermée par synchronisation par longueur, et par superposition par longueur. On a en particulier la famille des langages algébriques visibles. Il en est de même pour la famille F des automates synchronisés et de différence de longueur bornée; ces automates reconnaissent les langages contextuels.
Article: "Boolean Algebras by Length Recognizability" avec .D. Caucal, Models, Mindsets, Meta, 169-185, (2018).