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 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
- ,
où 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]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.
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 « --automaton » pour désigner un automate sur l'alphabet et à valeurs dans le demi-anneau . 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 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 .
- C'est l'automate de Sakarovitch 2009, Exercice 2.15, page 437.
- Peter Kostolányi, « On deterministic weighted automata », Information Processing Letters, vol. 140, , 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, , 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, , p. 1–31.
- Bénali Benzaghou, « Algèbres de Hadamard », Bull. Soc. Math. France, vol. 98, , p. 209–252 (lire en ligne, consulté le ).
- Jean-Paul Bézivin, « Suites récurrentes linéaires en caractéristique non nulle », Bull. Soc. Math. France, vol. 115, no 2, , p. 227–239 (lire en ligne, consulté le ).
- Jason Bell et Daniel Smertnig, « Noncommutative rational Pólya series », Selecta Mathematica New Ser., vol. 27, no 3, , article no 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é, [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, , 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 », , 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, (ISBN 978-0-12-234001-7)
- Jean Berstel et Christophe Reutenauer, Les séries rationnelles et leurs langages, Masson, , 132 p. (ISBN 9782225801372).
- Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, , 816 p. (ISBN 978-2-7117-4807-5) — Traduction anglaise avec corrections : (en) Jacques Sakarovitch, Elements of Automata Theory, Cambridge, Cambridge University Press, , 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, , 3e é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 » (no 12038), (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, , article no 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, , article no 114295 (DOI 10.1016/j.tcs.2023.114295)
- Manfred Droste et Werner Kuich, « Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings », Theoretical Computer Science, vol. 1002, , p. 114599 (DOI 10.1016/j.tcs.2024.114599 , lire en ligne, consulté le )