Universalité d'un langage rationnel
Le problème de déterminer si une expression rationnelle engendre le langage universel est PSPACE-complet.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 29 | Langages rationnels et automates finis. Exemples et applications2022 |
| 4 | 915 | Classes de complexité. Exemples.2021 |
Utilisateur : Emile
On peut se contenter du côté PSPACE-difficile, tant qu'on a l'idée pour le reste de la preuve.
Références :
Le Langage des machines - Floyd, Beigel