Universalité d'un langage rationnel

Ce développement montre que le problème d'universalité d'un langage rationnel ( est-ce que $L=\Sigma ^{*}$ ? ) est PSPACE-complet. Pour des raisons de temps le caractère PSPACE peut être admis ou mis dans le plan.

Le développement

pdf : Fichier:Pb Universalité.pdf

Recasements

• 909 - Langages Rationnels. Exemples et applications. ( pour cause d'utilisation abusive des expressions rationnelles)
• 915 - Classes de Complexité: exemples.
• (913 - Machines de Turing. Applications.)
•  ?

Références

• Floyd-Biegel
• Poly cours Cachan complexité (L3) par Serge Haddad