Non-Structural Subtype Entailment in Automata Theory
Autor: Joachim Niehren and Tim Priesnitz
Herausgeber:
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.
|