Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

Non-Structural Subtype Entailment in Automata Theory

Joachim Niehren, Tim Priesnitz

Fourth International Symposium on Theoretical Aspects of Computer Software, pp. 360--384, springer, October 2001

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.

Download PDF        Show BibTeX               

@INPROCEEDINGS{SubTypeEntailment:01,
  title = {Non-Structural Subtype Entailment in Automata Theory},
  author = {Joachim Niehren and Tim Priesnitz},
  year = {2001},
  month = {oct#{ 28-31}},
  publisher = {springer},
  booktitle = {Fourth International Symposium on Theoretical Aspects of Computer Software},
  series = {"LNCS"},
  pages = {{360--384}},
  address = {{Sendai, Japan}},
}

Login to edit