Jump to content

LOGCFL

From Wikipedia, the free encyclopedia

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:

See also

[edit]

References

[edit]
  1. ^ a b c Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002), The Complexity Theory Companion, Texts in Theoretical Computer Science: An EATCS Series, Springer, p. 280, doi:10.1007/978-3-662-04880-1, ISBN 9783662048801
  2. ^ Kapron, Bruce M., ed. (2023), Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, ACM Books, Morgan & Claypool, p. 124, ISBN 9798400707803
  3. ^ a b Gottlob, Georg; Leone, Nicola; Scarcello, Francesco (2001), "The complexity of acyclic conjunctive queries", Journal of the ACM, 48 (3): 431–498, doi:10.1145/382780.382783
  4. ^ Vortmeier, Nils; Kokkinis, Ioannis (2021), "The dynamic complexity of acyclic hypergraph homomorphisms", in Kowalik, Lukasz; Pilipczuk, Michal; Rzazewski, Pawel (eds.), Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers, Lecture Notes in Computer Science, vol. 12911, Springer, pp. 232–244, arXiv:2107.06121, doi:10.1007/978-3-030-86838-3_18, ISBN 978-3-030-86837-6
[edit]