Développement : Séparation par automate NP-complet

Détails/Enoncé :

Input : k entier et S,T deux langages finis.
Output : Existe t'il un automate A à k états qui sépare S et T.
Ce problème est NP-complet.
ref : Floyd,Biegel

Versions :

Pas de version pour ce développement.