Non-structural subtype entailment in automata theory
| Title: | Non-structural subtype entailment in automata theory |
|---|---|
| Authors: | Joachim Niehren; Tim Priesnitz |
| Contributors: | The Pennsylvania State University CiteSeerX Archives |
| Source: | http://hal.univ-lille3.fr/docs/00/53/65/40/PDF/SubTypeEntailment_02.pdf. |
| Publisher Information: | Springer-Verlag |
| Publication Year: | 2001 |
| Collection: | CiteSeerX |
| Description: | Decidability of non-structural subtype entailment is a long-standing open prob-lem 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 sub-type 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. Key words: programming languages, subtyping, finite automata, word equations. 1 |
| Document Type: | text |
| File Description: | application/pdf |
| Language: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.635.9158 |
| Availability: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.635.9158; http://hal.univ-lille3.fr/docs/00/53/65/40/PDF/SubTypeEntailment_02.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: | edsbas.7683385 |
| Database: | BASE |