Automate pondéré

En Informatique théorique, et particulièrement en théorie des automates, un automate fini pondéré est une généralisation des automates finis. Dans un automate fini usuel, qu'il soit déterministe ou non déterministe, les transitions ou flèches portent des étiquettes qui sont des lettres de l’alphabet sous-jacent. Dans un automate pondéré, toute transition porte de plus un certain poids. Ce poids peut être interprété comme le coût pour passer d'un état à un autre lorsque la transition est effectuée.

Définition mathématique[modifier | modifier le code]

Soient $K$ un demi-anneau, et soit $\Sigma$ un alphabet.

Un automate pondéré avec poids dans $K$ est composé des objets suivants :

un ensemble $Q$ fini d'états
une fonction de transition $\mu :Q\times \Sigma \times Q\to K$ à valeurs dans $K$ ,
une fonction de poids d'entrée $\lambda :Q\to K$ ,
une fonction de poids de sortie $\theta :Q\to K$ .

Un chemin dans un automate pondéré est une suite

(q_{0},a_{1},q_{1},a_{2},\ldots ,a_{n},q_{n})\

,

où $q_{0},\ldots ,q_{n}\in Q$ sont des états et $a_{1},\ldots ,a_{n}\in \Sigma$ sont des lettres. Le mot $a_{1}a_{2}\cdots a_{n}\$ est l'étiquette du chemin, et l'élément $\lambda (q_{0})\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})\theta (q_{n})$ du demi-anneau est son poids. Le poids est donc le produit du poids d'entrée du premier état par le produit des poids des transitions, multiplié par le poids de sortie du dernier état^[1]. Le poids d'un mot $w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ dans l’automate est la somme $\pi (w)$ des poids de tous les chemins étiquetés par $w$ . La fonction calculée par l’automate est la fonction qui à un mot associe son poids. On l'écrit aussi sous la forme d'une série formelle :

\sum _{w\in \Sigma ^{*}}\pi (w)\,w

.

Notation matricielle[modifier | modifier le code]

La fonction calculée par un automate pondéré s'exprime simplement avec une notation matricielle. Pour cela, on considère que l'ensemble d'états est $Q=\{1,\ldots ,n\}$ des entiers de 1 à $n$ . La fonction de transition définit, pour toute lettre $a$ , une matrice $\nu (a)$ d'ordre $n$ par

\nu (a)_{p,q}=\mu (p,a,q)

.

On étend $\nu$ en un morphisme de $\Sigma ^{*}$ dans les matrices d'ordre n par la formule

\nu (a_{1}a_{2}\cdots a_{n})=\nu (a_{1})\nu (a_{2})\cdots \nu (a_{n})

.

En considérant $\lambda$ comme un vecteur ligne, et $\theta$ comme un vecteur colonne, le poids d'un mot $w$ est alors simplement

\pi (w)=\lambda \nu (w)\theta

.

C'est pourquoi on trouve aussi la définition d'un automate pondéré comme triplet $(\lambda ,\nu ,\theta )$ .

Un premier exemple[modifier | modifier le code]

L'automate ci-contre^[2] a deux états. C'est un automate sur l'anneau des entiers $\mathbb {Z}$ . La représentation graphique indique que le vecteur d'entrée est $\lambda =(1\ 0)$ , le vecteur de sortie transposé est $\theta ^{t}=(0\ 1)$ , et les deux matrices de transition sont :

\nu (a)={\begin{pmatrix}1&1\\0&1\end{pmatrix}}

et

\nu (b)={\begin{pmatrix}1&-1\\0&1\end{pmatrix}}

Un calcul matriciel montre que pour un mot $w$ composé de $p$ lettres $a$ et de $q$ lettres $b$ , on a

\nu (w)={\begin{pmatrix}1&p-q\\0&1\end{pmatrix}}

.

Les vecteurs d'entrée et de sortie sélectionnent de coefficient d'indice (1,2), et on a donc

\pi (w)=p-q

pour un mot $w$ composé de $p$ lettres $a$ et de $q$ lettres $b$ . Les mots dont le poids est nul sont donc les mots qui ont autant de $a$ que de $b$ . En tant que langage formel, ce langage, comme son complémentaire, ne sont pas des langages réguliers. Ceci montre que les automates pondérés reconnaissent des objets bien plus généraux.

Autres exemples[modifier | modifier le code]

Demi-anneau de Boole. Le cas le plus simple est le demi-anneau de Boole $B$ composé de 0 et de 1. Un automate fini au sens usuel du terme peut être vu comme un automate pondéré à valeurs dans $B$ . Pour cela, on fixe :

le poids d'entrée d'un état est 1 s'il est initial, 0 sinon,
le poids d'une triplet (p,a,q) est 1 ou 0 selon que c'est une transition de l'automate ou non,
le poids de sortie d'un état est 1 s'il est final, 0 sinon.

Avec cette correspondance, le poids d'un chemin de l'automate pondéré est 1 exactement quand le chemin est un chemin réussi dans l’automate traditionnel et 0 sinon, et le poids d'un mot est 1 ou 0 selon qu'il est accepté ou non par l’automate.

Demi-anneau tropical. Un autre exemple souvent considéré est le demi-anneau tropical ${\mathcal {T}}=(\mathbb {R} \cup \infty ,\min ,+,\infty ,0)$ , où $\infty$ est l'élément neutre de l'addition représentée par $\min$ et 0 est l'élément neutre pour l'opération + jouant le rôle de la multiplication. Pour cette pondération, le poids d'un chemin est la somme des poids de ses étiquettes, et le poids d'un mot est le minimum des poids de tous les chemins étiquetés par ce mot.

Automates probabilistes et les Automates quantiques. Ce sont également des automates pondérées. Dans un automate probabiliste, les poids représentent des probabilités, et les matrices de la représentation doivent être stochastiques, dans une automate quantique, les matrices sont unitaires.

Les automates de Mealy et plus généralement les transducteurs finis également peuvent être vues comme des automates pondérées. Les poids sont alors les mots produits par les automates: plus précisément, si $\Delta$ est l'alphabet de sortie, l'ensemble des parties de $\Delta ^{*}$ , munies de la réunion et de la concaténation, est un demi-anneau. Le poids d'un mot est alors formé de l'ensemble des mots de sortie de tous le chemins d'une étiquette donnée.

Un cas particulier est constitué des automates pondérés déterministes qui se rapprochent des automates séquentiels^[3]^,^[4].

Théorème de Kleene-Schützenberger[modifier | modifier le code]

Le théorème de Kleene-Schützenberger est une extension du théorème de Kleene aux automates pondérés. Le théorème affirme qu'une série formelle en variables non commutatives à coefficients dans un demi-anneau est rationnelle si et seulement si elle est reconnue par un automate fini pondéré, dont les poids respectifs des étiquettes sont des éléments de ce demi-anneau^[5].

Séries de Pólya[modifier | modifier le code]

Les séries formelles rationnelles en variables non commutatives à coefficients dans un corps possèdent des propriétés arithmétiques remarquables liées à la nature arithmétique de leurs coefficients.

Une série à coefficients dans une corps K est appelée une série de Pólya si ses coefficients non nuls sont contenus dans un sous-groupe finiment engendré de K*.

Un théorème de Pólya de 1921^[6] décrit ces séries rationnelles dans le cas d'une variable. Il a été généralisé ensuite par Benali Benzaghou en 1970^[7] et Jean-Paul Bézivin^[8] en 1987, toujours pour une variable. Le cas de plusieurs variables a été décrit par et Daniel Smertnig et Jason Bell. Il s'énonce comme suit : Une série est une série de Pólya précisément lorsqu'elle est reconnue par un automate pondéré inambigu^[9].

Note historique[modifier | modifier le code]

Les automates finis pondérés, surtout considérés comme des séries formelles, ont été introduites comme généralisation des langages formels, par Marcel-Paul Schützenberger au début des années 1960^[10]. Une exposition systématique, sous forme de généralisation des automates usuels, a été présentée dans le traité de Samuel Eilenberg^[11]. Il a notamment introduit le terme « $K$ - $\Sigma$ -automaton » pour désigner un automate sur l'alphabet $\Sigma$ et à valeurs dans le demi-anneau $K$ . Plus récemment, le livre de Jacques Sakarovitch^[12] puis le manuel de Droste, Kuich et Vogler^[13] ont élargi le champ, et ont aussi inclus des applications pratiques.

Conférence biennale[modifier | modifier le code]

Tous les deux ans a lieu une conférence scientifique intitulée Weighted Automata: Theory and Applications (abrégée en WATA) consacrée aux automates pondérés. En 2020, la conférence a lieu à Marseille^[14].

Notes et références[modifier | modifier le code]

↑ Sakarovitch 2003 fait la différence entre le produit $\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})$ qu'il appelle l'étiquette ou le résultat, et la valeur $\lambda (q_{0})\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})\theta (q_{n})$ qu'il appelle le calcul. Droste, Kuich et Vogler 2009 appelle poids uniquement le produit $\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})$ .
↑ C'est l'automate de Sakarovitch 2009, Exercice 2.15, page 437.
↑ Peter Kostolányi, « On deterministic weighted automata », Information Processing Letters, vol. 140,‎ 2018, p. 42–47 (DOI 10.1016/j.ipl.2018.08.005).
↑ Peter Kostolányi, « Determinisability of unary weighted automata over the rational numbers », Theoretical Computer Science, vol. 898,‎ 4 janvier 2022, p. 110-131 (DOI 10.1016/j.tcs.2021.11.002).
↑ Pour des extensions et variantes, voir par exemple Droste, Kuich et Vogler 2009.
↑ George Pólya, « Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. », J. Reine Angew. Math., vol. 151,‎ 1921, p. 1–31.
↑ Bénali Benzaghou, « Algèbres de Hadamard », Bull. Soc. Math. France, vol. 98,‎ 1970, p. 209–252 (lire en ligne, consulté le 10 décembre 2019).
↑ Jean-Paul Bézivin, « Suites récurrentes linéaires en caractéristique non nulle », Bull. Soc. Math. France, vol. 115, n^o 2,‎ 1987, p. 227–239 (lire en ligne, consulté le 10 décembre 2019).
↑ Jason Bell et Daniel Smertnig, « Noncommutative rational Pólya series », Selecta Mathematica New Ser., vol. 27, n^o 3,‎ 2021, article n^o 34 (34 pages) (arXiv 1906.07271).
↑ Schützenberger 1961.
↑ Eilenberg 1974.
↑ Sakarovitch 2003.
↑ Droste, Kuich et Vogler 2009.
↑ Site de la conférence WATA 2020.

Bibliographie[modifier | modifier le code]

Ouvrages classiques

Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
Marcel-Paul Schützenberger, « On the definition of a family of automata », Information and Control, vol. 4,‎ 1961, p. 245–270 (lire en ligne).
Manfred Droste, Werner Kuich et Heiko Vogler (éditeurs), Handbook of Weighted Automata, Springer-Verlag, coll. « Monographs in theoretical computer science », 2009, xvii + 608 (ISBN 978-3-642-01491-8, DOI 10.1007/978-3-642-01492-5, zbMATH 1200.68001, SUDOC 139029907)
Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974 (ISBN 978-0-12-234001-7)

Jean Berstel et Christophe Reutenauer, Les séries rationnelles et leurs langages, Masson, 1984, 132 p. (ISBN 9782225801372).

Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5) — Traduction anglaise avec corrections : (en) Jacques Sakarovitch, Elements of Automata Theory, Cambridge, Cambridge University Press, 2009, 758 p. (ISBN 978-0-521-84425-3)
(en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)

Articles

Laure Daviaud, « Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases », dans Language and Automata Theory and Applications. LATA 2020, Springer, Cham, coll. « Lecture Notes in Computer Science » (n^o 12038), 2020 (ISSN 0302-9743, DOI 10.1007/978-3-030-40608-0_2), p. 17–32
Yongming Li, Qian Wang et Sanjiang Li, « On quotients of formal power series », Information and Computation, vol. 285, Part B,‎ 2022, article n^o 104874 (arXiv 1203.2236).
Florian Bruse, Maurice Herwig et Martin Lange, « Weights of formal languages based on geometric series with an application to automatic grading », Theoretical Computer Science, vol. 983,‎ 1^er février 2024, article n^o 114295 (DOI 10.1016/j.tcs.2023.114295)

Articles liés[modifier | modifier le code]

Portail de l'informatique théorique

[1] Sakarovitch 2003 fait la différence entre le produit $\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})$ qu'il appelle l'étiquette ou le résultat, et la valeur $\lambda (q_{0})\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})\theta (q_{n})$ qu'il appelle le calcul. Droste, Kuich et Vogler 2009 appelle poids uniquement le produit $\mu (q_{0},a_{1},q_{1})\cdots \mu (q_{n-1},a_{n},q_{n})$ .

[2] C'est l'automate de Sakarovitch 2009, Exercice 2.15, page 437.

[Kostolányi2018-3] Peter Kostolányi, « On deterministic weighted automata », Information Processing Letters, vol. 140,‎ 2018, p. 42–47 (DOI 10.1016/j.ipl.2018.08.005).

[Kostolányi2022-4] Peter Kostolányi, « Determinisability of unary weighted automata over the rational numbers », Theoretical Computer Science, vol. 898,‎ 4 janvier 2022, p. 110-131 (DOI 10.1016/j.tcs.2021.11.002).

[5] Pour des extensions et variantes, voir par exemple Droste, Kuich et Vogler 2009.

[6] George Pólya, « Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. », J. Reine Angew. Math., vol. 151,‎ 1921, p. 1–31.

[7] Bénali Benzaghou, « Algèbres de Hadamard », Bull. Soc. Math. France, vol. 98,‎ 1970, p. 209–252 (lire en ligne, consulté le 10 décembre 2019).

[8] Jean-Paul Bézivin, « Suites récurrentes linéaires en caractéristique non nulle », Bull. Soc. Math. France, vol. 115, n^o 2,‎ 1987, p. 227–239 (lire en ligne, consulté le 10 décembre 2019).

[9] Jason Bell et Daniel Smertnig, « Noncommutative rational Pólya series », Selecta Mathematica New Ser., vol. 27, n^o 3,‎ 2021, article n^o 34 (34 pages) (arXiv 1906.07271).

[10] Schützenberger 1961.

[11] Eilenberg 1974.

[12] Sakarovitch 2003.

[DKV-13] Droste, Kuich et Vogler 2009.

[14] Site de la conférence WATA 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg