Non-Structural Subtype Entailment in Automata Theory

Abstract : 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.
Type de document :
Communication dans un congrès
Naoki Kobayashi and Benjamin C. Pierce. 4th International Symposium on Theoretical Aspects of Computer Software, 2001, Sendai, Japan. Springer, 2215, pp.360--384, 2001, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536514
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 13:18:54
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : jeudi 17 février 2011 - 02:57:03

Fichier

pauto.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536514, version 1

Citation

Joachim Niehren, Tim Priesnitz. Non-Structural Subtype Entailment in Automata Theory. Naoki Kobayashi and Benjamin C. Pierce. 4th International Symposium on Theoretical Aspects of Computer Software, 2001, Sendai, Japan. Springer, 2215, pp.360--384, 2001, Lecture Notes in Computer Science. 〈inria-00536514〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

32