Hilfskellermaschine
aus Wikipedia, der freien Enzyklopädie
Eine Hilfskellermaschine (eng. auxilliary 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 finden Ivan H. Sudborough eine interessante Charakterisierung eines komplexitätstheoretischen Abschlusses der kontextfreien Sprachen. Das Modell wurde des weiteren von Eric Allender, Allan Borodin, Franz-Josef Brandenburg, Clemens Lautemann, Pierre McKenzie, Rolf Niedermeier, Peter Rossmanith, Thomas Schwentick, Martin Tompa, Heribert Vollmer und vielen anderen betrachtet und weiter untersucht.
Das interessante an diesem Berechnungsmodell besteht darin, dass es unserem Verständnis vom tatsächlichen Rechnen intuitiv entgegenkommt: Wenn wir uns niedersetzen und etwas größeres ausrechnen wollen, müssen wir uns organisieren; ein Teil unserer Organisation besteht darin, dass 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 ebenfalls deterministisch. Es gilt sogar, das nichtdeterministische Berechnungsmodell ist dem deterministischen nicht überlegen im Fall von diesen Hilfskellermaschinen.
Ivan H. Sudborough beschränkt den maximalen Zeitbedarf der Hilskellermaschinen polynomiell und charakterisiert den Abschluss der kontextfreien Sprachen unter logarithmischer Reduktion durch polynomialzeit beschränkte Hilfskellermaachinen mit logarithmischer Platzschranke. Hier gibt es sehr enge Beziehungen zu den Klassen AC und NC.
