Universalité d'un langage rationnel

De AgregmathKL
Aller à : navigation, rechercher

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