LOGCFL

LOGCFL

In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme die mit logarithmischen Speicheraufwand auf eine kontextfreie Sprache (engl. Context-Free Language) reduziert werden können.

Inhaltsverzeichnis

verschiedene Charakterisierungen

Neben der eigentlichen Definition gibt es noch einige äquivalente Charakterisierungen der Klasse LOGCFL:

Hilfskellermaschinen

Die Entscheidungsprobleme die eine nichtdeterministische Hilfskellermaschine mit logarithmisch platzbeschränktem Arbeitsband, einem Kellerspeicher und polynomiell beschränkter Laufzeit lösen kann. (von Ivan H.Sudborough)

Alternierende Turing Maschinen

Die Entscheidungsprobleme die mit einer Alternierenden Turing Maschinen mit logarithmischen Speicheraufwand und polynomiell beschränkter Baumgröße gelöst werden können.

Boolean circuits

Die Entscheidungsprobleme die durch Familien von "semi-unbounded Boolean circuits" mit einer durch O(log n) beschränkten Tiefe gelöst werden können. Diese Schaltkreise bestehen aus AND-Gates mit einem auf 2 beschränkten FANIN und OR-Gates mit beliebig großen FANIN.

Beziehung zu anderen Komplexitätsklassen

Aus der Definition von LOGCFL folgt, dass alle Sprachen aus LOGCFL in polynomieller Zeit entschieden werden können also LOGCFL ⊆ P. Ob diese Inklusion echt ist, ist ein wesentliches offenes Problem der Komplexitätstheorie. Weiterhin ist bekannt, dass LOGCFL ⊆ NC gilt.

AC0 ⊆ NC1 ⊆ L ⊆ NL ⊆ LOGCFL ⊆ AC1 ⊆ NC2 ⊆ P

Probleme in LOGCFL

  • Auswerten von azyklischen Boolean conjunctive queries
  • Homomorphie-Problem: Gibt es einen Homomorphismus zwischen zwei azyklischen relationalen Schemata.

Literatur

Ivan H. Sudburough: On the Tape Complexity of Context Free Languages. Journal of the ACM 25(3), pp405,414, 1978.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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. This class is situated between NL and AC1, in the sense that it contains… …   Wikipedia

  • LOGCFL — En complejidad computacional, LOGCFL es la clase de complejidad que contiene todos los problemas de decisión que pueden ser reducidos en espacio logarítmico a un lenguaje libre de contexto. Esta clase se sitúa entre NL y AC1, en el sentido que… …   Wikipedia Español

  • LOGCFL (Komplexitätsklasse) — In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme die mit logarithmischen Speicheraufwand auf eine kontextfreie Sprache (engl. Context Free Language) reduziert werden können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Komplexitätsklasse P — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • P-Vollständigkeit — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Ptime — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Komplexitätsklasse NP — NP (nichtdeterministisch polynomielle Zeit) ist eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge …   Deutsch Wikipedia

  • NP-Probleme — NP (nichtdeterministisch polynomielle Zeit) ist eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge …   Deutsch Wikipedia

  • Circuits over sets of natural numbers — Circuits over natural numbers is a mathematical model used in studying computational complexity theory. It is a special case of circuit, the object is a labeled directed acyclic graph the nodes of which evaluate to sets of natural numbers, the… …   Wikipedia

  • Conjunctive query — In database theory, a conjunctive query is a restricted form of first order queries. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first order queries can be written as… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”