| Title: |
Non-Structural Subtype Entailment in Automata Theory |
| Authors: |
Niehren, Joachim; Priesnitz, Tim |
| Contributors: |
Programming Systems Lab Saarland; Saarland University Saarbrücken; Naoki Kobayashi and Benjamin C. Pierce |
| Source: |
4th International Symposium on Theoretical Aspects of Computer Software; https://hal.inria.fr/inria-00536514; 4th International Symposium on Theoretical Aspects of Computer Software, 2001, Sendai, Japan. pp.360--384 |
| Publisher Information: |
HAL CCSD; Springer |
| Publication Year: |
2001 |
| Collection: |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
| Subject Terms: |
[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] |
| Subject Geographic: |
Sendai; Japan |
| Description: |
International audience ; 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. |
| Document Type: |
conference object |
| Language: |
English |
| Relation: |
inria-00536514; https://hal.inria.fr/inria-00536514; https://hal.inria.fr/inria-00536514/document; https://hal.inria.fr/inria-00536514/file/pauto.pdf |
| Availability: |
https://hal.inria.fr/inria-00536514; https://hal.inria.fr/inria-00536514/document; https://hal.inria.fr/inria-00536514/file/pauto.pdf |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.E7B0C1F4 |
| Database: |
BASE |