Textdokument
Die Analyse von Kellerstrukturen: Eine Reise durch 50 Jahre Forschung
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2015
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik, Bonn
Zusammenfassung
Vor 50 Jahren bewies J. R. Büchi, dass die Menge der erreichbaren Kellerinhalte eines Kellerautomaten eine reguläre Sprache bildet. Nur 5 Jahre später eröffnete M. O. Rabin mit seiner Theorie endlicher Automaten auf unendlichen Bäumen eine weiter greifende Perspektive, die in neuester Zeit zu überraschend starken algorithmischen Ergebnissen geführt hat, unter anderem für Systeme mit geschachtelten Kellern. Wir geben eine informelle Darstellung dieser Entwicklung und skizzieren aktuelle Forschungsfragen.