Hilfskellermaschine

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Eine Hilfskellermaschine (eng. auxiliary pushdown automaton) ist ein Berechnungsmodell aus der Komplexitätstheorie.

Die erste Erwähnung findet sich bei Stephen Cook 1971 im Journal of the ACM.

1978 gelang Ivan H. Sudborough die Charakterisierung eines komplexitätstheoretischen Abschlusses der kontextfreien Sprachen: Sudborough definiert die Klasse LOGCFL als Abschluss der Klasse der kontextfreien Sprachen unter logarithmisch platzbeschränkter Turing-Reduktion. Er zeigt, dass diese von logarithmisch platzbeschränkten Hilfskellermaschinen in polynomieller Zeit akzeptiert werden können. Das Modell wurde unter anderem von Eric Allender, Allan Borodin, Franz-Josef Brandenburg, Clemens Lautemann, Pierre McKenzie, Rolf Niedermeier, Peter Rossmanith, Thomas Schwentick, Martin Tompa und Heribert Vollmer weiter untersucht.

Eigenschaften

Wenn ein Mensch sich niedersetzen und etwas Größeres ausrechnen will, muss er alle Zwischenergebnisse nebeneinander auf dem Tisch ausbreiten. Irgendwann ist der Tisch voll und man beginnt Stapel anzulegen.

Der Stapel entspricht dem Pushdown, dem Kellerspeicher eines Kellerautomaten; der Platz auf dem Schreibtisch ist der Arbeitsspeicher. Offenbar kann man auf dem Stapel viel mehr unterbringen als auf dem Arbeitsspeicher. Allerdings sieht man die Dokumente im Stapel nicht mehr. Nur das oberste bleibt sichtbar.

Das Resultat von Stephen Cook lautet: Jede Sprache, die in polynomieller Zeit entschieden werden kann, kann von einer Hilfskellermaschine mit logarithmischer Platzbeschränkung und unbeschränktem Keller in exponentieller Zeit entschieden werden, sogar deterministisch. Zudem ist das nichtdeterministische Berechnungsmodell dem deterministischen im Fall von Hilfskellermaschinen nicht überlegen.

Ivan H. Sudborough beschränkt den maximalen Zeitbedarf der Hilfskellermaschinen polynomiell und charakterisiert den Abschluss der kontextfreien Sprachen unter logarithmischer Reduktion durch polynomialzeitbeschränkte Hilfskellermaschinen mit logarithmischer Platzschranke. Hier gibt es sehr enge Beziehungen zu den Komplexitätsklassen AC und NC.

Quellen

• Stephen A. Cook - Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM vol. 18, nr. 1 (January 1971)