Non-Structural Subtype Entailment in Automata Theory

Decidability of non-structural subtype entailment is a long-standing open problem in programming language theory. In this paper, we apply automata theoretic methods to characterize the problem equivalently by using regular expressions and word equations. This characterization induces new results on...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2003, Vol.169 (2), p.319-354
Main Authors: Niehren, Joachim, Priesnitz, Tim
Format: Article
Language:English
Subjects:
Computer Science
Programming Languages
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Decidability of non-structural subtype entailment is a long-standing open problem in programming language theory. In this paper, we apply automata theoretic methods to characterize the problem equivalently by using regular expressions and word equations. This characterization induces new results on non-structural subtype entailment, constitutes a promising starting point for further investigations on decidability, and explains for the first time why the problem is so difficult. The difficulty is caused by implicit word equations that we make explicit.
ISSN:0890-5401
1090-2651