Problème de séparation par automate : Différence entre versions
De AgregmathKL
m (a déplacé Problème de séparation par automates vers Problème de séparation par automate : On ne sépare que par un seul automate) |
|||
| Ligne 6 : | Ligne 6 : | ||
*[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par automate]] | *[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par automate]] | ||
*[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_psa.pdf | Problème de séparation par automate]] | *[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_psa.pdf | Problème de séparation par automate]] | ||
| + | |||
| + | Recasements : | ||
| + | * [[904 -- Problèmes NP-complets : exemples]] | ||
| + | * [[908 -- Automates Finis, exemples et applications]] | ||
| + | * [[909 -- Langages rationnels. Exemples et applications]] | ||
| + | * [[915 -- Classes de complexité : exemples]] | ||
Version du 11 avril 2012 à 17:29
On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet.
Version de Kévin 2012
Séparons les langages
Recasements :
