LOGCFL

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 AC¹, 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]

^ ^a ^b ^c Cite error: The named reference companion was invoked but never defined (see the help page).
^ Cite error: The named reference kapron was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference gls was invoked but never defined (see the help page).
^ Cite error: The named reference vk was invoked but never defined (see the help page).