Please use this identifier to cite or link to this item:
doi:10.22028/D291-25776
Title: | Non-structural subtype entailment in automata theory |
Author(s): | Niehren, Joachim Priesnitz, Tim |
Language: | English |
Year of Publication: | 2001 |
OPUS Source: | Proceedings of the Fourth International Symposium on Theoretical Aspects of Computer Software, TACS 2001, Sendai, Japan, October 29-31, 2001. - Berlin: Springer, 2001. (Lecture Notes in Computer Science; 2215), pp.360-384. |
SWD key words: | Algebraische Automatentheorie |
Free key words: | Automata Theory |
DDC notations: | 004 Computer science, internet |
Publikation type: | Conference Paper |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-2942 hdl:20.500.11880/25832 http://dx.doi.org/10.22028/D291-25776 |
Date of registration: | 12-Jul-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.