Automate fini inambigu

On peut tester si un automate fini non déterministe à m transitions est inambigu en temps ${\displaystyle O(m^{3})}$. On peut même calculer le degré d’ambiguïté, et savoir si l'ambiguïté est bornée, si elle croit polynomialement ou exponentiellement avec la longueur des mots[3].

Le problème d'inclusion consiste à tester si le langage reconnu par un automate ${\displaystyle A}$ est contenu dans le langage reconnu par un automate ${\displaystyle B}$. Le problème est bien entendu décidable. La question est celle de sa complexité.

Le problème de l'inclusion pour les automates inambigus est décidable en temps polynomial : il est dans la classe PTIME alors que ce même problème est PSPACE-complet pour les automates non déterministes[4] - [5]. C'est d'ailleurs ce problème, décrit par Meyer et Stockmeyer en 1972[6] qui est le premier problème de cette classe.

La démonstration de cette propriété utilise le fait que le produit cartésien de deux automates inambigus est également inambigu[4].

Le problème de l'universalité, c'est-à-dire de savoir si un automate accepte tous les mots, et le problème de l'équivalence, c'est-à-dire de savoir si deux automates acceptent les mêmes mots, sont tous deux dans la classe PTIME, par réduction au problème de l'inclusion.

Soient L, M des langages rationnels sur un alphabet commun, avec usc(L)=m et usc(M)=n. On a les résultats suivants[9] :

• image miroir : ${\displaystyle {\text{usc}}(L^{\sim })={\text{usc}}(L)}$, où ${\displaystyle L^{\sim }}$ est le langage miroir ;
• intersection : ${\displaystyle {\text{usc}}(L\cap M)\leq mn}$, et la borne est atteinte sur un alphabet à au moins 2 lettres.
• quotient gauche : ${\displaystyle {\text{usc}}(L^{-1}M)\leq 2^{n}-1}$, et la borne est atteinte sur un alphabet à au moins 2 lettres.
• quotient droit : ${\displaystyle {\text{usc}}(LM^{-1})\leq 2^{n}-1}$, et la borne est atteinte sur un alphabet à au moins 2 lettres.
• mélange :${\displaystyle {\text{usc}}(L{\text{ш}}\ M)\leq 2^{nm}-1}$, et la borne est atteinte sur un alphabet à au moins 5 lettres.
• produit : ${\displaystyle {\text{usc}}(LM)\leq 3/4\cdot 2^{n+m}-1}$, pourvu que ${\displaystyle n,m\geq 2}$, et la borne est atteinte sur un alphabet à au moins 6 lettres.
• étoile propre (opération plus) : ${\displaystyle {\text{usc}}(L)\leq 3/4\cdot 2^{m}-1}$, pourvu que ${\displaystyle m\geq 2}$, et la borne est atteinte sur un alphabet à au moins 3 lettres.
• étoile : ${\displaystyle {\text{usc}}(L)\leq 3/4\cdot 2^{m}}$, pourvu que ${\displaystyle m\geq 2}$, et la borne est atteinte sur un alphabet à au moins 3 lettres.

Il est intéressant de comparer la complexité des opérations sur les langages au moyen d' automates déterministes, d'automates inambigus et automates non déterministes. Pour cela, on introduit les notations :

• sc(L), nombre minimal d’états d’un automate déterministe reconnaissant le langage L.
• usc(L), comme ci-dessus le nombre minimal d’états d’un automate inambigu reconnaissant le langage L.
• nsc(L), nombre minimal d’états d’un automate non déterministe déterministe reconnaissant le langage L.

Dans la table suivante, les complexités sont résumées pour des langages donnés de complexité inambiguë n et m[9] :

Opération	sc	nsc	usc
miroir	${\displaystyle 2^{n}}$	${\displaystyle n+1}$	${\displaystyle n}$
intersection	${\displaystyle mn}$	${\displaystyle mn}$	${\displaystyle mn}$
quotient gauche	${\displaystyle 2^{n}-1}$	${\displaystyle n+1}$	${\displaystyle 2^{n}-1}$
quotient droit	${\displaystyle n}$	${\displaystyle n}$	${\displaystyle 2^{n}-1}$
étoile positive	${\displaystyle 3/4\cdot 2^{n}-1}$	${\displaystyle n}$	${\displaystyle 3/4\cdot 2^{n}-1}$
étoile	${\displaystyle 3/4\cdot 2^{n}}$	${\displaystyle n+1}$	${\displaystyle 3/4\cdot 2^{n}}$
mélange	${\displaystyle \geq 2^{(m-1)(n-1)}}$	${\displaystyle mn}$	${\displaystyle 2^{mn}}$
produit	${\displaystyle m\cdot 2^{n}}$	${\displaystyle m+n}$	${\displaystyle 3/4\cdot 2^{m+n}-1}$
complément	${\displaystyle 2^{n}}$	${\displaystyle n}$	${\displaystyle \leq 2^{0,79n+\log n}}$ ${\displaystyle \geq n^{d}\ \forall d}$[1]

Il existe une méthode générale pour calculer des minorants de la complexité inambigüe. Couplée avec la construction en général plus facile, d'un automate inambigu, elle fournit une borne inférieur à la complexité d'une opération sur les automates inambigus. La méthode est basée sur le calcul du rang d'une matrice associée à un automate ; elle a été développée par Schmidt dans une thèse non publiée de 1978, puis par Leung[10], et par Hromkovič et al.[11], et est reprise dans Jirásek et al.[9].

On considère un automate fini non déterministe ${\displaystyle {\mathcal {A}}=(Q,I,{\mathcal {F}},T)}$ sur un alphabet A, où ${\displaystyle I}$ et ${\displaystyle T}$ sont des ensembles d'états initiaux et terminaux.

Un état ${\displaystyle q}$ est dit accessible à partir de l'état ${\displaystyle p}$ par le mot ${\displaystyle w}$ s'il existe un chemin d'étiquette ${\displaystyle w}$ de ${\displaystyle p}$ à ${\displaystyle q}$. Un ensemble ${\displaystyle S\subseteq Q}$ d'états est dit accessible s'il existe un mot ${\displaystyle w}$ tel que ${\displaystyle S}$ est l'ensemble des états accessibles à partir d'un état initial par un chemin d'étiquette ${\displaystyle w}$. On dit qu'un ensemble ${\displaystyle P}$ d'états est coaccessible si ${\displaystyle P}$ est accessible dans l'automate transposé de ${\displaystyle {\mathcal {A}}}$[12].

Les ensembles non vides d'états qui sont accessibles ou coaccessibles sont notés

${\displaystyle {\mathcal {R}}=\{S\subseteq Q\mid S\ {\text{accessible}},S\neq \emptyset \}}$ et ${\displaystyle {\mathcal {C}}=\{P\subseteq Q\mid P\ {\text{accessible}},P\neq \emptyset \}.}$

On a alors la propriété suivante :

L'automate ${\displaystyle {\mathcal {A}}}$ est inambigu si et seulement si deux ensembles d'états ${\displaystyle S}$ de ${\displaystyle {\mathcal {R}}}$ et ${\displaystyle P}$ de ${\displaystyle {\mathcal {C}}}$ quelconques ont au plus un élément en commun : ${\displaystyle |S\cap R|\leq 1.}$

On s'en sert pour établir le résultat suivant, qui relie la complexité du langage au rang d'une matrice :

Pour vérifier que la complexité de l'intersection atteint bien la valeur ${\displaystyle mn}$ pour des automates à ${\displaystyle m}$ et ${\displaystyle n}$ états, on considère des langages et automates particuliers, et on montre que l'automate pour l'intersection, qui a ${\displaystyle mn}$ états, ne peut être remplacé par un automate inambigu plus petit à l'aide du théorème.

On considère les langages sur l'alphabet ${\displaystyle \{a,b\}}$ définis par ${\displaystyle K=\{w\mid |w|_{a}=m-1\}}$ et ${\displaystyle L=\{w\mid |w|_{b}=n-1\}}$, pour ${\displaystyle m}$ et ${\displaystyle n}$ fixés. Ce sont donc les langages de mots contenant exactement ${\displaystyle m-1}$ lettres ${\displaystyle a}$ respectivement exactement ${\displaystyle n-1}$ lettres ${\displaystyle b}$. Des automates inambigus (déterministe et incomplets) acceptant ces langages sont ${\displaystyle {\mathcal {A}}=(Q_{A},0,m-1,F_{A})}$ et ${\displaystyle {\mathcal {B}}=(Q_{B},0,n-1,F_{B})}$, avec ${\displaystyle Q_{A}=\{0,\ldots ,m-1\}}$, ${\displaystyle Q_{B}=\{0,\ldots ,n-1\}}$, et les flèches de ${\displaystyle F_{A}}$ composées de ${\displaystyle (i,a,i+1)}$ pour ${\displaystyle 0\leq i\leq m-2}$ et ${\displaystyle (j,b,j)}$ pour tout j, et pour ${\displaystyle F_{B}}$ composées de ${\displaystyle (i,a,i)}$ pour tout i et ${\displaystyle 0\leq i\leq m-1}$ et ${\displaystyle (j,b,j+1)}$ pour ${\displaystyle 0\leq j\leq n-2}$.

L’automate produit est l’automate ${\displaystyle (Q_{A}\times Q_{B},(0,0),(m-1,n-1),F)}$, où l'ensemble de flèches ${\displaystyle F}$ est composé des flèches ${\displaystyle ((p,q),a,(p',q'))}$ pour ${\displaystyle (p,a,p')\in F_{A}}$ et ${\displaystyle (q,a,q')\in F_{B}}$.

Tout ensemble singleton ${\displaystyle (i,j)}$ est accessible dans l’automate produit (par ${\displaystyle a^{i}b^{j}}$), et est coaccessible (par ${\displaystyle a^{m-1-i},b^{n-1-j}}$), et seuls des ensembles singletons sont accessibles ou coaccessibles. La matrice ${\displaystyle M}$ de l’énoncé est donc la matrice identité d’ordre ${\displaystyle mn}$, ce qui donne la borne inférieure pour l'intersection[9].