Campus Event Calendar
Event Entry
New for: D3
What and Who
Charakterisierung nicht-struktureller Untertyp-Subsumption in der Automaten-Theorie
Tim Priesnitz
Seminar des Graduiertenkollegs
AG 1, AG 2, AG 3, AG 4
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 30 April 2001
16:00
-- Not specified --
36 - Informatik
306
Saarbrücken
Abstract
Charakterisierung nicht-struktureller Untertyp-Subsumption in der
Automaten-Theorie
Entscheidbarkeit von nicht-struktureller Untertyp-Subsumption (NSSE) ist
ein offenes Problem aus der theoretischen Informatik. Es wurde von Remy
und Pottier (ICFP96) im Kontext von Typinferenz für moderne
Programmiersprachen aufgeworfen, und seitdem vielfach untersucht
(Henglein, Rehof, Sue, Aiken, etc).
In diesem Vortrag charakterisiere ich NSSE erstmals durch reguläre
Ausdrücke und Wortgleichungen. Wortgleichungen sind bekannterweise
schwer zu lösen, da sie nicht-reguläre Sprachen beschreiben können. Die
neue Charakterisierung zeigt somit zum erstenmal, warum NSSE so schwer
ist: Es liegt an impliziten Wortgleichungen, die meine Charakterisierung
explizit macht. Ich hoffe, dass sich die Entscheidbarkeit von NSSE mit
Resultaten über Wortgleichungen zeigen lässt.
Spezielle Vorkenntnisse im Bereich der Unifikations- und Typ-Theorie
setze ich nicht voraus.
Alle InteressentInnen sind zu dem Vortrag herzlich eingeladen.
Contact
Uelkue Coruh
--email hidden
passcode not visible
logged in users only