LOGCFL
Template:Short description Template:Use list-defined references Template:Use dmy dates 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.Template:R This class is closed under complementation.Template:R It is situated between NL and AC1, in the sense that it contains the formerTemplate:R and is contained in the latter.Template:R Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs:
- evaluating acyclic Boolean conjunctive queriesTemplate:R
- checking the existence of a homomorphism between two acyclic relational structuresTemplate:R
- checking the existence of solutions of acyclic constraint satisfaction problemsTemplate:R
LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time.[1]
See also
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "Citation/CS1".
Cite error: <ref> tag with name "companion" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "gls" defined in <references> is not used in prior text.
Cite error: <ref> tag with name "kapron" defined in <references> is not used in prior text.
<ref> tag with name "vk" defined in <references> is not used in prior text.Script error: No such module "Check for unknown parameters".