LOGCFL
Template:Short description Template:Use list-defined references Script error: No such module "Unsubst". In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language.[1]Template:R/superscript This class is closed under complementation.[1]Template:R/superscript It is situated between NL and AC1, in the sense that it contains the former[1]Template:R/superscript and is contained in the latter.[2]Template:R/superscript Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs:
- evaluating acyclic Boolean conjunctive queries[3]Template:R/superscript
- checking the existence of a homomorphism between two acyclic relational structures[4]Template:R/superscript
- checking the existence of solutions of acyclic constraint satisfaction problems[3]Template:R/superscript
LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time.[5]
See also
References
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".