Langage unaire — Wikipédia

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.
{1^k | 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, Berman^[1] 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 creux^[2] : s'il existe un langage creux qui est NP-complet, alors P = NP.

Notes et références

↑ Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, p. 63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.
↑ S. 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.

v · m

Théorie des automates, des langages formels et des grammaires formelles

Hiérarchie de Chomsky	Grammaire	Langage	Automate
Type-0	Grammaire sans restriction	Langage récursivement énumérable Langage récursif	Machine de Turing Machine de Turing qui s'arrête toujours
Type-1	Grammaire contextuelle Grammaire indexée Grammaire d'arbres adjoints	Langage contextuel Langage indexé Grammaire d'arbres adjoints	Automate linéairement borné Automate à piles emboîtées Automate à piles intégrées
Type-2	Grammaire non contextuelle ou grammaire algébrique Grammaire non contextuelle déterministe	Langage non contextuel ou langage algébrique Langage algébrique déterministe Langage à pile visible	Automate à pile Automate à pile déterministe Automate à pile visible
Type-3	Grammaire régulière ou grammaire rationnelle	Langage rationnel Langage sans étoile	Automate fini déterministe Monoïde syntaxique apériodique

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique