Universalité d'un langage rationnel

De AgregmathKL
Révision de 26 février 2015 à 21:16 par Mathias Millet (discuter | contributions)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
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
Récupérée de « https://minerve.bretagne.ens-cachan.fr/index.php?title=Universalité_d%27un_langage_rationnel&oldid=2701 »