Universalité d'un langage rationnel : Différence entre versions
De AgregmathKL
(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... ») |
|||
| Ligne 13 : | Ligne 13 : | ||
* Floyd-Biegel | * Floyd-Biegel | ||
* Poly cours Cachan complexité (L3) par Serge Haddad | * Poly cours Cachan complexité (L3) par Serge Haddad | ||
| + | |||
| + | |||
| + | [[Category: Développement de la leçon 909]] | ||
| + | [[Category: Développement de la leçon 915]] | ||
Version actuelle en date du 26 février 2015 à 21:16
Ce développement montre que le problème d'universalité d'un langage rationnel ( est-ce que 
? ) 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
