Automate pondéré

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

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

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

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

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

où ${\displaystyle q_{0},\ldots ,q_{n}\in Q}$ sont des états et ${\displaystyle a_{1},\ldots ,a_{n}\in \Sigma }$ sont des lettres. Le mot ${\displaystyle a_{1}a_{2}\cdots a_{n}\ }$ est l'étiquette du chemin, et l'élément ${\displaystyle \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 ${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ dans l’automate est la somme ${\displaystyle \pi (w)}$ des poids de tous les chemins étiquetés par ${\displaystyle 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 :

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

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 ${\displaystyle Q=\{1,\ldots ,n\}}$ des entiers de 1 à ${\displaystyle n}$. La fonction de transition définit, pour toute lettre ${\displaystyle a}$, une matrice ${\displaystyle \nu (a)}$ d'ordre ${\displaystyle n}$ par

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

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

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

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

${\displaystyle \pi (w)=\lambda \nu (w)\theta }$.

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

Un automate pondéré.

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

${\displaystyle \nu (a)={\begin{pmatrix}1&1\\0&1\end{pmatrix}}}$ et ${\displaystyle \nu (b)={\begin{pmatrix}1&-1\\0&1\end{pmatrix}}}$

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

${\displaystyle \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

${\displaystyle \pi (w)=p-q}$

pour un mot ${\displaystyle w}$ composé de ${\displaystyle p}$ lettres ${\displaystyle a}$ et de ${\displaystyle q}$ lettres ${\displaystyle b}$. Les mots dont le poids est nul sont donc les mots qui ont autant de ${\displaystyle a}$ que de ${\displaystyle 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.

Demi-anneau de Boole. Le cas le plus simple est le demi-anneau de Boole ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {\mathcal {T}}=(\mathbb {R} \cup \infty ,\min ,+,\infty ,0)}$, où ${\displaystyle \infty }$ est l'élément neutre de l'addition représentée par ${\displaystyle \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 ${\displaystyle \Delta }$ est l'alphabet de sortie, l'ensemble des parties de ${\displaystyle \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].

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].

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].

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 « ${\displaystyle K}$-${\displaystyle \Sigma }$-automaton » pour désigner un automate sur l'alphabet ${\displaystyle \Sigma }$ et à valeurs dans le demi-anneau ${\displaystyle 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.

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].

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).

• Automate fini non déterministe
• Automate fini
• Théorie des automates
• Automate de Mealy
• Automate de Moore
• Transducteur fini

• Portail de l'informatique théorique