LOGCFL
Encyclopedia
In computational complexity theory
, LOGCFL is the complexity class
that contains all decision problem
s that can be reduced in logarithmic space to a context-free language
. This class is situated between NL
and AC
1, in the sense that it contains the former and is contained in the latter. Problems that are complete
for LOGCFL include many problems whose instances can be characterized by acyclic
hypergraph
s:
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, LOGCFL is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
that contains all decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be reduced in logarithmic space to a context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
. This class is situated between NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
and AC
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O and a polynomial number of unlimited-fanin AND and OR gates....
1, in the sense that it contains the former and is contained in the latter. Problems that are complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for LOGCFL include many problems whose instances can be characterized by acyclic
Acyclic
Acyclic can refer to:* In chemistry, a compound which is not cyclic, e.g. alkanes and acyclic aliphatic compounds* In mathematics:** A graph without a cycle, especially*** A directed acyclic graph...
hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s:
- evaluating acyclic Boolean conjunctive queriesBoolean conjunctive queryIn the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form R_1 \wedge \cdots \wedge R_n, where each R_i is a relation symbol and each t_i is a tuple of variables and constants; the number of elements in t_i...
- checking the existence of a homomorphismHomomorphismIn abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
between two acyclic relational structures - checking the existence of solutions of acyclic constraint satisfaction problemConstraint satisfaction problemConstraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
s