Universalité d'un langage rationnel

De AgregmathKL
Révision de 2 novembre 2011 à 16:55 par Basile (discuter | contributions) (Page créée avec « Ce développement montre que le problème d''''universalité d'un langage rationnel''' ( est-ce que <math>L = \Sigma^*</math> ? ) est PSPACE-complet. Pour des raisons de temp... »)

(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.ens-rennes.fr/index.php?title=Universalité_d%27un_langage_rationnel&oldid=358 »