Zoo de complexité pour les langues unaires

25

Bien sûr, certains résultats de complexité peuvent s'effondrer pour les langues unaires, mais je me demande s'il existe quelque part une enquête résumant les résultats connus dans ce cas: une sorte de zoo de complexité pour les langues unaires. Connaissez-vous une telle référence?

cc.complexity-theory reference-request big-list J.-E. Épingle
la source
7
Bien sûr, on ne sait pas s'il existe un langage unaire NP-complet. Voir ceci pour en savoir plus: en.wikipedia.org/wiki/…
Ryan
Pas exactement ce que vous cherchez, mais voici un mini zoo avec des langues réductibles en langues unaires. arxiv.org/abs/1212.3282
Niall Murphy

Réponses:

23

Il n'y a pas encore de référence de style zoo, mais une récente étude théorique des automates de Giovanni Pighizzini m'a été utile, en particulier les diapositives de son exposé.

András Salamon
la source
12

Une question intéressante sur les classes de complexité sur un alphabet unaire qui ne figure pas dans les références ci-dessus est la force de la classe #P 1 de Valiant , la classe des problèmes de comptage sur un alphabet unaire (voir http://epubs.siam.org/doi/ abs / 10.1137 / 0208032 ). On ne sait pas grand-chose de sa puissance, bien qu'il ait des problèmes naturels complets et, comme les langues unaires, possède des circuits de taille polynomiale.

Paul Beame
la source