# 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

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

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

L'automate ci-contre 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

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$^,$.

## Théorème de Kleene-Schützenberger

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.

## Séries de Pólya

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 décrit ces séries rationnelles dans le cas d'une variable. Il a été généralisé ensuite par Benali Benzaghou en 1970 et Jean-Paul Bézivin 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.

## Note historique

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. Une exposition systématique, sous forme de généralisation des automates usuels, a été présentée dans le traité de Samuel Eilenberg. 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 puis le manuel de Droste, Kuich et Vogler ont élargi le champ, et ont aussi inclus des applications pratiques.

## Conférence biennale

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.