Diskussion:Hilfskellermaschine

Bevor beschrieben werden sollte, was an diesem Modell "interessant" ist, sollte erstmal das Modell an sich beschrieben werden. Auch ist wohl die lange (und sehr rote) Namensliste überflüssig. Also, Überarbeitung ist hier dringend nötig, es ist leider sehr unklar, wo jetzt der Unterschied zu einem "normalen" Kellerautomaten ist, etc. ... Gruß --eo !? 19:59, 4. Dez 2005 (CET)

Ich werde mich der Problematik annehmen. Vorab schon einmal: Eine Kellerautomat erlaubt nur den Zugriff auf das oberste Element im Kellerspeicher. Das kann im Stapelautomat anders sein. Hier steht man neben dem Stapel und kann alle Einträge sehen.

Wie gesagt, ich kümmere mich drum. Kann ein paar Wochen dauern.

Das Konzept der Hilfskellermaschine ist von zentraler Bedeutung. Es gibt sicherlich mehr als 20 Publikationen, die sich damit befassen. Das besondere ist einerseits, das Speicherplatz in Speicherplatz und Kellerspeicher aufgespaltet werden kann und dabei der Speicheplatz erheblich (logarithmisch klein) verkleinert wird. Allerdings wächst dafür der Zeitaufwand. Die Klasse LOGCFL dagegen kann mit demselben Modell erkannt werden - aber in polynomieller Zeit. Da P=LOGCFL eine offene Frage ist und das auch mit der Parallelisierbarkeit der Probleme in P und LOGCFL zusammenhängt, ist das von besonderer Relevanz. --bunt (Diskussion) 03:10, 29. Okt. 2020 (CET)