Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536540
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Saturday, February 5, 2011 - 12:51:17 PM
Last modification on : Thursday, February 21, 2019 - 10:52:45 AM
Long-term archiving on: : Friday, May 6, 2011 - 2:16:12 AM

File

SubTypeEntailment_02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536540, version 1

Collections

Citation

Joachim Niehren, Tim Priesnitz. Non-Structural Subtype Entailment in Automata Theory. Information and Computation, Elsevier, 2003, 169 (2), pp.319-354. ⟨inria-00536540⟩

Share

Metrics

Record views

165

Files downloads

111