Automate de Parikh

En informatique théorique, et notamment en théorie des automates, un automate de Parikh est un automate fini non déterministe dont les transitions comportent des vecteurs d’entiers naturels qui permettent de tester si la somme des vecteurs d'un calcul satisfait une contrainte semi-linéaire. L'intérêt de cette famille d'automates est qu'elle possède d'autres caractérisations équivalentes, sous forme de machine de Turing et sous une forme plus algébrique, dite RCM.

Description informelle

Un automate de Parikh est un automate fini dont les transitions sont étiquetées par des couples ${\displaystyle (a,v)}$, où ${\displaystyle a}$ est une lettre de l’alphabet d’entrée et ${\displaystyle v}$ est un vecteur de ${\displaystyle \mathbb {N} ^{d}}$, pour un entier ${\displaystyle d}$. Un chemin est une suite

${\displaystyle q_{0}\xrightarrow {a_{1},v_{1}} q_{1}\xrightarrow {a_{2},v_{2}} \cdots q_{n-1}\xrightarrow {a_{n},v_{n}} q_{n}}$

de transitions qui calcule le mot ${\displaystyle a_{1}\cdots a_{n}}$ et le vecteur ${\displaystyle v_{1}+\cdots +v_{n}}$, où la somme est faite composante par composante. La condition d’acceptation est donnée par un ensemble d’états terminaux et un ensemble semi-linéaire. Un chemin est un calcul réussi si, partant de l’état initial, il atteint un état final et si son vecteur appartient à l’ensemble semi-linéaire donné.

Les automates de Parikh ont été introduits en 2003 dans l’étude de la logique du second ordre^[1]. Ces automates acceptent les mêmes langages formels que les machines de Turing à compteurs à renversements bornées (en anglais « reversal bounded »)^[2]. Cette famille coïncide à son tour avec une classe définie par Massazza sous le nom de classe RCM^[3].

Exemple

L’automate de l'introduction^[4], avec la contrainte ${\displaystyle \{(n_{1},n_{2},n_{1}+n_{2}\mid n_{1},n_{2}\geq 0\}}$, accepte l’ensemble des mots ${\displaystyle w}$ sur l’alphabet ${\displaystyle \{a,b,c\}}$ qui commence et finissent par un ${\displaystyle a}$, et tels que ${\displaystyle |w|_{a}+|w|_{b}=|w|_{c}}$. `

Automates de Parikh

Ensemble semi-linéaire

Un sous-ensemble de ${\displaystyle \mathbb {N} ^{d}}$ est linéaire s'il est de la forme

${\displaystyle u_{0}+u_{1}\mathbb {N} +\cdots +u_{k}\mathbb {N} =\{u_{0}+t_{1}u_{1}+\ldots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}}$

pour des vecteurs ${\displaystyle u_{0},\ldots ,u_{m}}$. C'est donc l'ensemble des combinaisons linéaires, à coefficients entiers naturels, d'un ensemble fini de vecteurs de ${\displaystyle \mathbb {N} ^{d}}$, auxquels est ajouté le vecteur ${\displaystyle u_{0}}$. Par exemple, pour ${\displaystyle d=3}$, l'ensemble ${\displaystyle (1,0,0)+(1,1,1)\mathbb {N} =\{(n+1,n,n)|n\in \mathbb {N} \}}$ est un ensemble linéaire très simple.

Un sous-ensemble de ${\displaystyle \mathbb {N} ^{d}}$ est semi-linéaire s'il est une union finie de parties linéaires. Tout ensemble semi-linéaire possède une représentation inambigue, où les unions sont disjointes et où les écritures comme combinaisons linéaires sont uniques.

Définition des automates

Un automate de Parikh de dimension ${\displaystyle d\geq 1}$ est un tuple ${\displaystyle {\mathcal {A}}=(\Sigma ,Q,q_{I},F,C,\Delta )}$, où

• ${\displaystyle \Sigma }$ est l'alphabet,
• ${\displaystyle Q}$ est l'ensemble d'états
• ${\displaystyle q_{I}\in Q}$ est l'état initial
• ${\displaystyle F\subset Q}$ est l’ensemble des états terminaux
• ${\displaystyle C\subset \mathbb {N} ^{d}}$ est l'ensemble des contraintes semi-linéaires
• ${\displaystyle \Delta \subset Q\times (\Sigma \times \mathbb {N} ^{d})\times Q}$ est la relation de transition.

Un chemin dans l'automate est une suite

${\displaystyle q_{0}\xrightarrow {a_{1},v_{1}} q_{1}\xrightarrow {a_{2},v_{2}} \cdots q_{n-1}\xrightarrow {a_{n},v_{n}} q_{n}}$

où, pour ${\displaystyle 1\leq i\leq n}$, le triplet ${\displaystyle (q_{i-1),(a_{i},v_{i}}q_{i})}$ est dans ${\displaystyle \Delta }$. L'étiquette de ce chemin est le couple ${\displaystyle (a_{1}\cdots a_{n},v_{1}+\cdots +v_{n})}$. Le chemin est réussi ou acceptant si ${\displaystyle q_{0}=q_{I}}$, ${\displaystyle q_{n}\in F}$ et si de plus le vecteur ${\displaystyle v_{1}+\cdots +v_{n}}$ est dans ${\displaystyle C}$. Dans ce cas, le mot ${\displaystyle w=a_{1}\cdots a_{n}}$ est accepté ou reconnu par l'automate ${\displaystyle {\cal {A}}}$. Le langage reconnu par ${\displaystyle {\cal {A}}}$ est noté ${\displaystyle L({\cal {A)}}}$.

Automates inambigus

Un automate de Parikh est faiblement inambigu^[4] si, pour tout mot, il existe au plus un chemin réussi^[5]. L'automate de la figure ci-contre est faiblement inambigu. Il a pour ensemble semi-linéaire de contraintes l'ensemble ${\displaystyle C=\{(n_{1},n_{2},n_{3})\mid n_{1}=n_{2}+n_{3}{\text{ et }}n_{2}<n_{3}\}}$. Si on oublie la partie semi-linéaire, l'automate sous-jacent, qui reconnait le langage ${\displaystyle c^{*}(a+b)^{+}}$, est en revanche un automate fini ambigu.

La famille des langages reconnus par des automates de Parikh faiblement inambigus est fermée par intersection ; la fermeture par union ou par complémentation est une question encore ouverte^[4]. Il existe des langages inhéremment faiblement inambigus au sens que tout automate de Parikh les reconnaissants est faiblement ambigu^[4].

Caractérisation par machines de Turing

Une machine de Turing à ${\displaystyle k}$ compteurs est une machine de Turing qui possède, en plus de ses attributs usuels, un ensemble de ${\displaystyle k}$ compteurs^[2]. La machine, dans l'état ${\displaystyle q}$ et en lisant une lettre ${\displaystyle a}$ sur sa bande d'entrée, peut examiner ses compteurs, et incrémenter ou décrémenter certains de ses compteurs. La machine ne connaît pas la valeur de ses compteurs mais sait tester s'ils sont nuls ou non. Une machine de Turing est à renversements bornés (en anglais « reversal bounded ») si sa tête de lecture ne peut changer de direction qu'un nombre borné de fois ; plus précisément, elle est ${\displaystyle (m,n)}$-bornée si elle peut changer de direction au plus ${\displaystyle m}$ fois, et si chaque compteur ne peut alterner l'incrémentation et la décrémentation au plus ${\displaystyle n}$ fois. Une machine de Turing, à ${\displaystyle k}$ compteurs et ${\displaystyle (m,n)}$-bornée est inambigue si, de plus, chaque mot possède au plus un calcul acceptant.

L'égalité de ces familles de langages n'est plus vraie dans le cas déterministe^[6]. En revanche, la version inambigue est valide :

Langages RCM

Paolo Massazza^[3] a introduit en 1993 une famille de langages appelée RCM^[7]. La construction rappelle, mais de loin, la représentation des langages algébriques par langages de Dyck. Ces langages sont définis comme suit.

On se donne un alphabet ${\displaystyle A=\{a_{1},\ldots ,a_{d}\}}$ totalement ordonné avec ${\displaystyle a_{1}<\cdots <a_{d}}$. À tout ensemble semi-linéaire ${\displaystyle C}$ de dimension ${\displaystyle d}$ on associe le langage ${\displaystyle [C]=\{w\in A^{*}\mid (|w|_{a_{1}},\ldots ,|w|_{a_{d}})\in C\}}$. Ce langage est l'ensemble des mots dont les nombres d'occurrences de chaque lettre satisfont les contraintes de ${\displaystyle C}$. Si par exemple ${\displaystyle C_{0}=\{(n,m,n,m)|n,m\geq 0\}}$ et l'alphabet est ${\displaystyle a<b<c<d}$, le langage ${\displaystyle [C_{0}]}$est l'ensemble de tous les mots sur ces 4 lettres qui ont autant d'occurrences de ${\displaystyle a}$ que de ${\displaystyle c}$ et autant de ${\displaystyle b}$ que de ${\displaystyle d}$.

Par définition, un langage ${\displaystyle L}$ sur un alphabet ${\displaystyle \Sigma }$ appartient à la famille RCM s'il existe un langage rationnel ${\displaystyle R}$ sur ${\displaystyle A=\{a_{1},\ldots ,a_{d}\}}$, un ensemble semi-linéaire ${\displaystyle C\subset \mathbb {N} ^{d}}$ et un morphisme préservant la longueur ${\displaystyle \mu :A^{*}\to \Sigma ^{*}}$ qui est injectif sur ${\displaystyle R\cap [C]}$ tels que

${\displaystyle L=\mu (R\cap [C])}$.

Par exemple, le langage ${\displaystyle L_{abab}=\{a^{n}b^{m}a^{n}b^{m}|n,m\geq 0\}}$ est dans la famille RCM parce qu'il s'écrit sous la forme ${\displaystyle L_{abab}=\mu (R\cap [C_{0}])}$, où ${\displaystyle C_{0}}$ est l'ensemble semi-linaire défini ci-dessus et ${\displaystyle \mu }$ identifie ${\displaystyle a}$ et ${\displaystyle c}$ respectivement ${\displaystyle b}$ et ${\displaystyle d}$.

Le lien entre les langages RCM est les automates de Parikh est le résultat suivant :

Notes et références

Bibliographie

• Alin Bostan, Arnaud Carayol, Florent Koechlin et Cyril Nicaud, « Weakly-unambiguous Parikh automata and their link to holonomic series », 47th International Colloquium on Automata, Languages, and Programming,‎ 2020, p. 114:1-114:16 (DOI 10.4230/LIPIcs.ICALP.2020.114, lire en ligne, consulté le 28 mai 2020).
• Michaël Cadilhac, Alain Finkel et Pierre McKenzie, « Affine Parikh automata », RAIRO Theor. Inf. and Applic., vol. 46, n^o 4,‎ 2012, p. 511-545 (DOI 10.1051/ita/2012013).
• Michaël Cadilhac, Alain Finkel et Pierre McKenzie, « Unambiguous constrained automata », Int. J. Found. Comput. Sci., vol. 24, n^o 7,‎ 2013, p. 1099-1116 (DOI 10.1142/S0129054113400339).
• Giusi Castiglione et Paolo Massazza, « On a class of languages with holonomic generating functions », Theoretical Computer Science, vol. 658,‎ 2017, p. 74–84 (DOI 10.1016/j.tcs.2016.07.022).

• Thomas Colcombet, « Unambiguity in automata theory », dans Jeffrey Shallit et Alexander Okhotin, Descriptional Complexity of Formal Systems - 17th International Workshop, Springer, coll. « LectureNotes in Computer Science » (n^o 9118), 2015 (DOI 10.1007/978-3-319-19225-3_1), p. 3–18.

• Oscar H. Ibarra, « Reversal-bounded multicounter machines and their decision problems », Journal of the ACM, vol. 25, n^o 1,‎ 1978, p. 116-133 (DOI 10.1145/322047.322058).

• Felix Klaedtke et Harald Rueß, « Monadic second-order logics with cardinalities », dans Automata, Languages and Programming, 30th International Colloquium, Springer, coll. « LectureNotes in Computer Science » (n^o 2719), 2003 (DOI 10.1007/3-540-45061-0_54), p. 74–84.
• Paolo Massazza, « Holonomic functions and their relation to linearly constrained languages », RAIRO - Informatique Théorique et Applications, vol. 27, n^o 2,‎ 1993, p. 149-161 (DOI 10.1051/ita/1993270201491).

• Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen et Martin Zimmermann, « Parikh Automata over Infinite Words », Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, vol. 250 « 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) »,‎ 2022, p. 40:1–40:20 (ISBN 978-3-95977-261-7, DOI 10.4230/LIPIcs.FSTTCS.2022.40, lire en ligne)

• Enzo Erlich, Shibashis Guha, Ismaël Jecker et Karoliina Lehtinen, « History-deterministic Parikh Automata », arXiv,‎ 16 septembre 2022 (arXiv 2209.07745)

Articles liés

• Automate fini
• Machine de Turing
• Théorème de Parikh

• Portail de l'informatique théorique