Problème de séparation par automate

On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet.

PSA est NP-complet

• PSA est NP-complet
• PSA est NP-complet

Version de Kévin 2012

Séparons les langages

• Problème de séparation par automate
• Problème de séparation par automate

Recasements :

• 908 -- Automates Finis, exemples et applications
• 909 -- Langages rationnels. Exemples et applications.
• 915 -- Classes de complexité : exemples.