Hilfskellermaschine

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln 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. 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 wir uns niedersetzen und etwas größeres ausrechnen wollen, müssen wir alle Zwischenergebnisse nebeneinander auf dem Tisch ausbreiten. Irgendwann ist der Tisch voll und wir beginnen Stapel anzulegen.

Der Stapel entspricht unserem Pushdown, dem Kellerspeicher eines Kellerautomaten; der Platz auf unserem Schreibtisch ist unser Arbeitsspeicher. Offenbar können wir auf dem Stapel viel mehr unterbringen als auf dem Arbeitsspeicher. Allerdings sehen wir 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 Klassen 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)