Agreg-maths Dvpts Leçons Livres Retours
Se connecter S'inscrire

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
Rajouter une version
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