Logo des Repositoriums
 
Textdokument

Die Analyse von Kellerstrukturen: Eine Reise durch 50 Jahre Forschung

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2015

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.

Beschreibung

Thomas, Wolfgang (2015): Die Analyse von Kellerstrukturen: Eine Reise durch 50 Jahre Forschung. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial. Gesellschaft für Informatik, Bonn. PISSN: 1614-3213. ISBN: 978-3-88579-426-4. pp. 55-64. Jena. 14. November 2014

Schlagwörter

Zitierform

DOI

Tags