Automate pondéré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 un demi-anneau, et soit un alphabet.

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

  • un ensemble fini d'états
  • une fonction de transition à valeurs dans ,
  • une fonction de poids d'entrée ,
  • une fonction de poids de sortie .

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

,

sont des états et sont des lettres. Le mot est l'étiquette du chemin, et l'élément 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 dans l’automate est la somme des poids de tous les chemins étiquetés par . 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 :

.

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 des entiers de 1 à . La fonction de transition définit, pour toute lettre , une matrice d'ordre par

.

On étend en un morphisme de dans les matrices d'ordre n par la formule

.

En considérant comme un vecteur ligne, et comme un vecteur colonne, le poids d'un mot est alors simplement

.

C'est pourquoi on trouve aussi la définition d'un automate pondéré comme triplet .

Un premier exemple[modifier | modifier le code]

Un automate pondéré.

L'automate ci-contre[2] a deux états. C'est un automate sur l'anneau des entiers . La représentation graphique indique que le vecteur d'entrée est , le vecteur de sortie transposé est , et les deux matrices de transition sont :

et

Un calcul matriciel montre que pour un mot composé de lettres et de lettres , on a

.

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

pour un mot composé de lettres et de lettres . Les mots dont le poids est nul sont donc les mots qui ont autant de que de . 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 composé de 0 et de 1. Un automate fini au sens usuel du terme peut être vu comme un automate pondéré à valeurs dans . 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 , où est l'élément neutre de l'addition représentée par 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 est l'alphabet de sortie, l'ensemble des parties de , 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.

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

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[4]. Une exposition systématique, sous forme de généralisation des automates usuels, a été présentée dans le traité de Samuel Eilenberg[5]. Il a notamment introduit le terme « --automaton » pour désigner un automate sur l'alphabet et à valeurs dans le demi-anneau . Plus récemment, le livre de Jacques Sakarovitch[6] puis le manuel de Droste, Kuich et Vogler[7] ont élargi le champ, et ont aussi inclus des applications pratiques.

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

  1. Sakarovitch 2003 fait la différence entre le produit qu'il appelle l'étiquette ou le résultat, et la valeur qu'il appelle le calcul. Droste, Kuich et Vogler 2009 appelle poids uniquement le produit .
  2. C'est l'automate de Sakarovitch 2009, Exercice 2.15, page 437.
  3. Pour des extensions et variantes, voir par exemple Droste, Kuich et Vogler 2009.
  4. Schützenberger 1961.
  5. Eileberg 1974.
  6. Sakarovitch 2003.
  7. Droste, Kuich et Vogler 2009.

Bibliographie[modifier | modifier le code]

  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, (ISBN 978-2-7117-4807-5) — Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press, (ISBN 978-0-52184425-3)

Articles liés[modifier | modifier le code]