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 , où  est une lettre de l’alphabet d’entrée et  est un vecteur de , pour un entier . Un chemin est une suite 
  
de transitions qui calcule le mot  et le vecteur , 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. Ces automates acceptent les mêmes langages formels que les machines de Turing à compteurs à renversements bornées (en anglais « reversal bounded »). Cette famille coïncide à son tour avec une classe définie par Massazza sous le nom de classe RCM.

Exemple 

L’automate de l'introduction, avec la contrainte , accepte l’ensemble des mots  sur l’alphabet  qui commence et finissent par un , et tels que .
`

Automates de Parikh

Ensemble semi-linéaire 

Un sous-ensemble de  est linéaire s'il est de la forme
 
pour des vecteurs . C'est donc l'ensemble des combinaisons linéaires, à coefficients entiers naturels, d'un ensemble fini de vecteurs de , auxquels est ajouté le vecteur . Par exemple, pour , l'ensemble  est un ensemble linéaire très simple.

Un sous-ensemble de  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  est un tuple , où
  est l'alphabet,
  est l'ensemble  d'états
  est l'état initial
  est l’ensemble des états terminaux
  est l'ensemble des contraintes semi-linéaires
  est la relation de transition.

Un chemin dans l'automate est une suite 
  
où, pour , le triplet  est dans . Létiquette de ce chemin est le couple . Le chemin est réussi ou acceptant si ,  et si de plus le vecteur   est dans . Dans ce cas, le mot  est accepté ou reconnu par l'automate . Le langage reconnu par  est noté .

Automates inambigus 

Un automate de Parikh est faiblement inambigu si, pour tout mot, il existe au plus un chemin réussi. L'automate de la figure ci-contre  est faiblement inambigu. Il a pour ensemble semi-linéaire de contraintes l'ensemble . Si on oublie la partie semi-linéaire, l'automate sous-jacent, qui reconnait le langage , 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. Il existe des langages inhéremment faiblement inambigus au sens que tout automate de Parikh les reconnaissants est faiblement ambigu.

Caractérisation par machines de Turing 
Une machine de Turing à  compteurs est une machine de Turing qui possède, en plus de ses attributs usuels, un ensemble de  compteurs. La machine, dans l'état  et en lisant une lettre  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 -bornée si elle peut changer de direction au plus  fois, et si chaque compteur ne peut alterner l'incrémentation et la décrémentation au plus  fois. Une machine de Turing, à  compteurs et -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. En revanche, la version inambigue est valide :

Langages RCM 

Paolo Massazza a introduit en 1993 une famille de langages appelée RCM. 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  totalement ordonné avec . À tout ensemble semi-linéaire  de dimension  on associe le langage . Ce langage est l'ensemble des mots dont les nombres d'occurrences de chaque lettre satisfont les contraintes de . Si par exemple  et l'alphabet est , le langage est l'ensemble de tous les mots sur ces 4 lettres qui ont autant d'occurrences de  que de  et autant de  que de . 

Par définition, un langage  sur un alphabet  appartient à la famille RCM s'il existe un langage rationnel  sur , un ensemble semi-linéaire  et un morphisme préservant la longueur  qui est injectif sur  tels que
.
Par exemple, le langage  est dans la famille RCM parce qu'il s'écrit sous la forme , où  est l'ensemble semi-linaire défini ci-dessus et  identifie  et  respectivement  et .

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

Notes et références

Bibliographie 
  .
  .
  .
  .

  .

  .

  .
  .

Articles liés 
 Automate fini
 Machine de Turing
 Théorème de Parikh

Automates finis et langages réguliers
Théorie des automates