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^[1]. 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.

1. ↑ I.H. Sudborough: Time and tape bounded auxiliary pushdown automata. In Mathematical Foundations of Computer Science 1977 pp 493-503, LNCS volume 53