Message-ID: <4E06A937DADC3842ACE4D3A1096A9EAC0384DB@JANUS.eecs.berkeley.edu> From: George Necula <necula@EECS.Berkeley.EDU> Subject: TODAY: PS Seminar Date: Mon, 22 Oct 2001 12:49:30 -0700 Just a last minute reminder that Tim Priesnitz will be giving a PS seminar today at 4pm in Soda 310: 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