Séparation par automate NP-complet
Input : k entier et S,T deux langages finis.\rOutput : Existe t'il un automate A à k états qui sépare S et T.\rCe problème est NP-complet.\r
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 909 | Langages rationnels et automates finis. Exemples et applications.2017 |
| 5 | 26 | Classes P et NP. Problèmes NP-complets. Exemples.2022 |
| 5 | 29 | Langages rationnels et automates finis. Exemples et applications2022 |
Utilisateur : Admin
Références :
Le Langage des machines - Floyd, Beigel