LOGCFL

Last updated

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:

Contents

LOGCFL is the set of decision problems solvable by nondeterministic auxiliary pushdown automata in log space and polynomial time. [5]

See also

References

  1. 1 2 3 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. 1 2 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
  5. ↑ Sudborough, I. H. (July 1978). "On the Tape Complexity of Deterministic Context-Free Languages". Journal of the ACM. 25 (3): 405–414. doi:10.1145/322077.322083. ISSN   0004-5411.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.