En théorie de la complexité, LOGCFL (pour Logarithmically Reducible to context-free language en anglais) désigne la classe des problèmes réductibles en espace logarithmique à un langage hors contexte. On a NL ⊆ LOGCFL ⊆ AC1.
Exemple
Problèmes dans LOGCFL Le problème d'évaluation d'un circuit booléen planaire et monotone (pas de portes NON) est dans LOGCFL.
Notes et références
Catégorie:Classe de complexité