https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=LOGCFLLOGCFL - Versionsgeschichte2026-05-24T13:11:56ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=LOGCFL&diff=398508&oldid=previmported>Aka: /* Literatur */ Leerzeichen vor Zahl eingefügt2025-08-12T07:37:13Z<p><span class="autocomment">Literatur: </span> Leerzeichen vor Zahl eingefügt</p>
<p><b>Neue Seite</b></p><div>In der [[Komplexitätstheorie]] bezeichnet '''LOGCFL''' die [[Komplexitätsklasse]] der Entscheidungsprobleme, die mit [[Logarithmisch platzbeschränkte Reduktion|logarithmischem Speicheraufwand]] auf eine [[kontextfreie Sprache]] ({{enS|context-free language}}) reduziert werden können.<br />
<br />
== Verschiedene Charakterisierungen ==<br />
Neben der eigentlichen Definition gibt es noch einige äquivalente Charakterisierungen der Klasse LOGCFL:<br />
<br />
=== Hilfskellermaschinen ===<br />
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]]).<br />
<br />
=== Alternierende Turing-Maschinen ===<br />
Die Entscheidungsprobleme, die mit einer [[Alternierende Turingmaschine|alternierenden Turing-Maschinen]] mit logarithmischem Speicheraufwand und polynomiell beschränkter Baumgröße gelöst werden können.<br />
<br />
=== Boolean circuits ===<br />
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-Gattern mit einem auf 2 beschränkten Fan-in und OR-Gattern mit beliebig großem Fan-in.<br />
<br />
== Beziehung zu anderen Komplexitätsklassen ==<br />
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.<br />
<br />
{{Kasten |style=display:table |Text=AC<sup>0</sup> ⊆ [[NC (Komplexitätsklasse)|NC]]<sup>1</sup> ⊆ [[L (Komplexitätsklasse)|L]] ⊆ [[NL (Komplexitätsklasse)|NL]] ⊆ '''LOGCFL''' ⊆ AC<sup>1</sup> ⊆ [[NC (Komplexitätsklasse)|NC]]<sup>2</sup> ⊆ [[P (Komplexitätsklasse)|P]]}}<br />
<br />
== Probleme in LOGCFL ==<br />
* Auswerten von azyklischen Boolean conjunctive queries<br />
* Homomorphie-Problem: Gibt es einen Homomorphismus zwischen zwei azyklischen relationalen Schemata?<br />
<br />
== Literatur ==<br />
* Ivan H. Sudburough: ''On the Tape Complexity of Context Free Languages''. In: ''Journal of the ACM'', 1978, 25(3), S. 405, 414.<br />
<br />
== Weblinks ==<br />
* {{Complexity Zoo|LOGCFL|L#logcfl}}<br />
<br />
[[Kategorie:Komplexitätsklasse]]<br />
[[Kategorie:Abkürzung]]</div>imported>Aka