🤖 Automates Pondérés Commutatifs 🚇

Une fois n’est pas coutume, je vais parler de la théorie des automates. Plus précisément, je vais montrer 4 preuves complètement différentes d’un même résultat sur les automates pondérés. Ce billet a le double usage de servir de référence pour ce résultat qui est connu, mais n’est pas facilement citable, mais aussi de sortir ces preuves de notes et d’échanges oraux pour ne plus y penser par la suite.

Dans la mesure du possible, je vais rendre ces résultats « auto-contenus », Avant de rentrer dans les détails et l’historique de la notion d’automate pondéré, on peut déjà dire que c’est un modèle de calcul qui sert à représenter des fonctions de type \(\Sigma^* \to \mathbb{F}\) où \(\Sigma\) est un alphabet fini et \(\mathbb{F}\) un (semi-)anneau. Pour simplifier la présentation des preuves, je vais me restreindre au cas où \(\mathbb{F} = \mathbb{C}\), et je laisse le soin au lecteur de généraliser les résultats à d’autres anneaux.

La question qui nous intéresse ici est de savoir si une telle fonction \(f \colon \Sigma^* \to \mathbb{C}\) est commutative, c’est-à-dire, si pour tout mot \(u \in \Sigma^*\), pour toute permutation \(\sigma\) des lettres de \(u\), on a \(f(u) = f(\sigma(u))\).

Exemple. Un exemple typique de fonction commutative est la fonction qui compte le nombre de lettres \(a\) dans un mot \(u\). En effet, si on permute les lettres de \(u\), le nombre de \(a\) ne change pas.

Non-Exemple. Un exemple typique de fonction non-commutative est la fonction qui compte le nombre de fois où le sous-mot \(ab\) apparaît dans un mot \(u\). En effet, \(f(ab) = 1\), mais \(f(ba) = 0\).

Dans ce billet, nous allons donc donner plusieurs algorithmes pour décider si une fonction \(f\) calculée par un automate pondéré est commutative ou non.

Automates pondérés

Avant de parler du résultat en question, je vais commencer par définir ce qu’est un automate pondéré. Et comme toutes les preuves que je vais donner n’utilisent pas le même modèle de calcul, je vais présenter les trois définitions utiles pour ce billet. Les fonctions calculées par les automates pondérés étaient déjà connues dans les années 70 et les travaux de Schützenberger (1962). Depuis, un certain nombre d’ouvrages de référence ont été écrits à leur sujet (Berstel and Reutenauer 1988, 2010; Sakarovitch 2009; Droste, Kuich, and Vogler 2009).

Les trois définitions présentées ci-après sont équivalentes, et les transformations entre ces trois modèles sont faisables algorithmiquement.

Définition 1: Un automate pondéré… un automate avec des pondérations

Un automate pondéré est un automate fini qui a des pondérations sur les arcs. Formellement, un automate pondéré est un quintuplet \((Q, \Sigma, \delta, I, F)\) où

• \(Q\) est un ensemble fini d’états,
• \(\Sigma\) est un alphabet fini,
• \(\delta \colon Q \times \Sigma \times Q \to \mathbb{C}\) est une relation de transition pondérée,
• \(I \subseteq Q\) est un ensemble d’états initiaux,
• \(F \colon Q \to \mathbb{C}\) est une fonction finale.

À tout mot d’entrée \(u \in \Sigma^*\), un tel automate possède un certain nombre de calculs possibles : ce sont les suites d’états \(q_0 \xrightarrow{u_1} q_1 \xrightarrow{u_2} \cdots \xrightarrow{u_n} q_n\) avec \(q_0 \in I\). La valeur d’un tel calcul est le produit des pondérations des transitions empruntées avec la valeur de la fonction finale, c’est-à-dire \(\delta(q_0, u_1, q_1) \cdot \delta(q_1, u_2, q_2) \cdots \delta(q_{n-1}, u_n, q_n) \cdot F(q_n)\). La fonction associée à un automate pondéré est la fonction qui associe à un mot d’entrée \(u\) la somme des valeurs de tous les calculs possibles pour \(u\).

Exemple. La fonction \(f\) qui associe à \(u\) le nombre de \(a\) dans \(u\) peut se représenter comme suit à l’aide d’un automate pondéré. \(Q = \{q_0, q_1\}\), \(\Sigma = \{a, b\}\), \(\delta(q_0, a, q_0) = 1\), \(\delta(q_0, b, q_0) = 0\), \(\delta(q_0, a, q_1) = 1\), \(\delta(q_0, b, q_1) = 0\), \(\delta(q_1, a, q_1) = 1\), \(\delta(q_1, b, q_1) = 0\), \(I = \{q_0\}\), \(F(q_0) = 0\), \(F(q_1) = 1\).

Définition 2: Une version algèbre linéaire

On utilisera la notation \(\mathcal{M}_{n}(\mathbb{C})\) pour désigner l’algèbre des matrices carrées de taille \(n\) à coefficients complexes. Une représentation linéaire d’un automate pondéré est donnée par un triplet \((I, \mu, F)\), où morphisme \(\mu \colon (\Sigma^*, \cdot) \to (\mathcal{M}_{n}(\mathbb{C}), \times)\), \(I\) est une matrice de taille \(n \times 1\), \(F\) est une matrice de taille \(1 \times n\).

Muni de cette représentation, on peut définir la fonction \(f \colon \Sigma^* \to \mathbb{C}\) associée à l’automate pondéré comme \(f(u) = F \mu(u) I\).

Exemple. La fonction \(f\) qui associe à un mot \(u\) le nombre de \(a\) dans \(u\) peut se représenter comme suit à l’aide d’une représentation linéaire. On considère \(\mu(a) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\), \(\mu(b) = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}\), \(I = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\), \(F = \begin{pmatrix} 0 & 1 \end{pmatrix}\).

Définition 3: Une algèbre différentielle

Lorsque l’on a une fonction \(f \colon \Sigma^* \to \mathbb{C}\), on peut définir les opérateurs de dérivation à gauche et à droite \(\partial_a^L(f)(u) = f(au)\) et \(\partial_a^R(f)(u) = f(ua)\).

Une fonction \(f\) est finiment différentielle si elle appartient à un espace vectoriel de dimension fini de fonctions allant de \(\Sigma^*\) dans \(\mathbb{C}\), qui est stable par les opérateurs de dérivation à gauche et à droite.

Preuve(s) de la décidabilité de la commutativité

Étant donné une fonction \(f \colon \Sigma^* \to \mathbb{C}\) calculée par un automate pondéré, on veut savoir si \(f\) est commutative. Dans une majorité des preuves suivantes, on utilisera le fait que l’égalité de deux automates pondérés est décidable (Berstel and Reutenauer 2010, Chapitre 2, Corollaire 3.6).

Preuve 1: Permutations et générateurs

L’idée est de tester si \(f = f \circ \delta\), pour toute fonction \(\delta\) qui permute les lettres du mot d’entrée. Le principal problème est qu’il y a une infinité de telles fonctions. Un second problème est que, si \(f\) est calculée par un automate pondéré, il n’est pas immédiat que \(f \circ \delta\) le soit aussi. La solution au problème principal est de se restreindre à deux permutations : on teste si \(f \circ \tau_{1,2} = f\) et si \(f \circ \sigma = f\), où \(\tau_{1,2}\) permute les deux premières lettres d’un mot et \(\sigma\) échange la première et la dernière lettre d’un mot.

Lemme. Si \(f \circ \tau_{1,2} = f \circ \sigma = f\) alors \(f\) est commutative.

Pour résoudre notre second problème, on utilise la présentation des automates pondérés sous forme de fonctions finiment différentielles.

Lemme. Si \(f\) est finiment différentielle alors \(f \circ \tau_{1,2}\) et \(f \circ \sigma\) sont finiment différentielles.

On a donc un algorithme pour décider si une fonction \(f\) calculée par un automate pondéré est commutative.

Preuve 2: Minimisation

On calcule une représentation linéaire minimale \((I, \mu, F)\) associée à la fonction \(f\). On teste si \(\mu(ab) = \mu(ba)\) pour tout \(a, b \in \Sigma\). Vérifions tout d’abord que cette condition est suffisante.

Lemme. Si \(\mu(ab) = \mu(ba)\) pour tout \(a, b \in \Sigma\) alors \(f\) est commutative.

Pour l’instant, nous n’avions pas utilisé la minimalité de la représentation linéaire. On va utiliser le fait que pour toute représentation linéaire minimale de dimension \(n\), tout vecteur de \(\mathbb{C}^n\) est accessible et co-accessible ; c’est-à-dire que \(\mathbb{C}^n\) est généré en tant qu’espace vectoriel par les vecteurs de la forme \(I \mu(w)\) où \(w \in \Sigma^*\), et que symétriquement, \(\mathbb{C}^n\) est généré en tant qu’espace vectoriel par les vecteurs de la forme \(\mu(w) F\) où \(w \in \Sigma^*\).

Lemme. Si \(f\) est commutative alors \(\mu(ab) = \mu(ba)\) pour tout \(a, b \in \Sigma\).

Preuve 3: Uniformisation

Au lieu d’observer des propriétés d’une représentation minimale de \(f\), on va construire une version commutative de \(f\) et tester l’égalité avec \(f\). Plus précisément, nous allons calculer \(f \circ \text{sort}\) où \(\text{sort}\) est une fonction qui trie les lettres d’un mot. On teste si \(f \circ \text{sort} = f\). J’utilise en boîte noire le lemme suivant, pour lequel je n’ai pas de référence précise à citer.

Lemme. Soit \(g\) une fonction régulière et \(f\) calculée par un automate pondéré. Alors \(f \circ g\) est calculée par un automate pondéré.

Il reste à vérifier que si \(f \circ \text{sort} = f\) alors \(f\) est commutative, ce qui est immédiat.

Lemme. Si \(f \circ \text{sort} = f\) alors \(f\) est commutative.

Preuve 4: Équations algébriques

Étant donné une fonction \(f\) calculée par une représentation linéaire de la forme \((I, \mu, F)\), on veut tester si pour tous mots \(x,y,z,t\), on a \(I \mu(xyzt) F = I \mu(xzyt) F\). Par linéarité, cela revient à décider si pour tous mots \(x,y,z,t\), on a \(I (\mu(x)\mu(y)\mu(z)\mu(t) - \mu(x)\mu(z)\mu(y)\mu(t)) F = 0\). Cette équation est polynomiale en les coefficients de \(\mu(x), \mu(y), \mu(z), \mu(t)\). Notons \(P\) ce polynôme possédant \(4 \times n^2\) inconnues.

La clôture de Zariski d’un ensemble \(E\) de matrices est le plus petit ensemble contentant \(E\) de matrices \(M\) telles que pour tout polynôme \(P\) en les coefficients de \(M\), si \(P\) s’annule sur \(E\), alors \(P(M) = 0\). Si on considère \(E = \{ \mu(u) \mid u \in \Sigma^* \}\), qui est un semigroupe de matrices finiment engendré par les matrices \(\mu(a)\) où \(a \in \Sigma\), alors la clôture de Zariski de \(E^4\) doit contenir notre polynôme \(P\).

Théorème (Hrushovski et al. 2018). On peut calculer la clôture de Zariski d’un semigroupe de matrice finiment généré. Et décider si un polynôme \(P\) est dans cette clôture.

Notre algorithme est alors le suivant : calculer la clôture de Zariski de \(E = \{ \mu(u) \mid u \in \Sigma^* \}\). De ce calcul, on peut déduire la clôture de Zariski de \(E^4\), et décider si \(P\) s’annule sur cette clôture.

Conclusion

Nous avons vu quatre algorithmes pour décider si une fonction \(f\) calculée par un automate pondéré est commutative ou non. Ces algorithmes sont basés sur des techniques très variées et toutes utiles dans certains contextes.