LOGCFL
Jump to navigation
Jump to search
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] This class is closed under complementation.[1] It is situated between NL and AC1, in the sense that it contains the former[1] and is contained in the latter.[2] Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs:
- evaluating acyclic Boolean conjunctive queries[3]
- checking the existence of a homomorphism between two acyclic relational structures[4]
- checking the existence of solutions of acyclic constraint satisfaction problems[3]
LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time.[5]
See also
[edit | edit source]References
[edit | edit source]- ^ a b c Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).