En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1.
Exemple
{1, 11, 1111, 1111111} est un langage unaire. {1k | k est premier} est un langage unaire.
Théorie de la complexité La classe de complexité de tous les langages unaires s'appelle TALLY. TALLY est inclus dans P/poly. En 1978, BermanPiotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, . Springer-Verlag. Lecture Notes in Computer Science #62. 1978. a montré que s'il existe un langage unaire qui est NP-complet, alors P = NP. Les langages unaires sont des langages creux, et ce résultat a été généralisé par Manahey aux langages creuxS. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982. : s'il existe un langage creux qui est NP-complet, alors P = NP.
Notes et références
Catégorie:Langage formel