Modèles de machines à compteurs non ambiguës

Modèles de machines à compteurs non ambiguës

Automates de Parikh faiblement non ambigus

Automate de Parikh, calcul acceptant, faible non-ambiguïté Nous introduisons dans cette section les automates de Parikh étudiés dans [KR02], ainsi que leur version faiblement non ambiguë. De façon informelle, un automate de Parikh est un automate dont les transitions sont étiquetées par un couple lettrevecteur. Lors d’un calcul de l’automate, on concatène les lettres rencontrées dans les transitions, et on additionne les vecteurs, composante par composante.

Un chemin de l’automate est donc étiqueté par un couple mot-vecteur, et est appelé calcul acceptant s’il commence dans un état initial, termine dans un état « nal, et si le vecteur somme Modèles de machines à compteurs non ambiguës 162 6 Modèles de machines à compteurs non ambiguës Le lecteur est invité à appartient à un ensemble semilinéaire lire le chapitre 1 des préliminaires pour la dé!nition d’un ensemble semilinéaire. d’acceptation associé à l’automate.

De façon plus formelle : Définition 6.1 (Automate de Parikh [KR02, KR03]). I Un automate de Parikh de dimension d > 1 est un tuple A = (Σ, Q, qI , F, C, ∆), où Σ désigne l’alphabet, Q l’ensemble d’états, qI 2 Q est l’état initial, et F ✓ Q l’ensemble des états « naux. En »n C ✓ N d Voir la sous-section 1.1.3 est l’ensemble semilinéaire des préliminaires pour la dé!nition d’un ensemble semilinéaire. d’acceptation, et ∆ ✓ Q ⇥ (Σ ⇥ N d ) ⇥ Q est l’ensemble des transitions. Un calcul de l’automate est une séquence q0 a1,v1 

#elques propriétés de clôture

Cette section arrive un peu trop tôt dans le chapitre, ou la thèse, car nous ne disposons pas à ce stade de su#samment d’outils pour faire certaines preuves. J’ai décidé cependant de rassembler ici quelques propriétés de (non) clôture des automates de Parikh faiblement non ambigus, car elle seraient sinon dispersées tout au long du chapitre et du suivant.

Il faut donc voir cette section comme une annonce de résultats, qui répond à certaines interrogations classiques que l’on se pose lorsque l’on introduit une classe d’automates. Par ailleurs, elle permet aussi de mieux comparer la classe des automates de Parikh faiblement non ambigus avec celle des automates de Parikh non ambigus présentés à la section suivante. Bien entendu, nous avons fait soigneusement attention à ne pas insérer par erreur des boucles d’interdépendances avec les preuves du prochain chapitre.

Dans un premier temps, nous énonçons quelques propriétés de clôture élémentaires : Proposition 6.7 (Quelques propriétés de clôture). I Soient L1 et L2 deux langages de Parikh faiblement non ambigus sur un alphabet Σ. Soit w un mot dans Σ ⇤ . Alors : a. L’intersection L1 \ L2 est un langage de Parikh faiblement non ambigu. b. Le langage quotient w.