Message-ID: <4E06A937DADC3842ACE4D3A1096A9EAC03848B@JANUS.eecs.berkeley.edu>
From: George Necula <necula@EECS.Berkeley.EDU>
Subject: PS Seminar announcement
Date: Thu, 18 Oct 2001 14:33:28 -0700
Hi,
This coming Monday (Oct 22) Tim Priesnitz, visiting us from University
Saarland (Germany, will give a talk at 4pm in Soda 310. His web page is at
www.ps.uni-sb.de/~tim.
TITLE
Non-Structural Subtype Entailment in Automata Theory
ABSTRACT
Decidability of non-structural subtype entailment (NSSE)
is a long-standing, open problem in programming language
theory. It was first raised by Remy and Pottier in the
context of type inference and since then NSSE has been
investigated numerous times (Henglein, Rehof, Sue, Aiken,
etc.).
In my talk, I characterize NSSE by regular expressions and
word equations. It is well known that word equations are
rather difficult to solve because they are capable of
describing non-regular languages.
My characterization shows for the first time why solving
NSSE is so difficult - the reason is NSSE hides implicit
word equations. My characterization then makes these word
equations explicit. I show how to solve a fragment of NSSE
by using Makanin's word equation result.
This archive was generated by hypermail 2b30 : 11/04/02 PST