Please use this identifier to cite or link to this item: doi:10.22028/D291-25763
Title: Non-structural subtype entailment in automata theory
Author(s): Niehren, Joachim
Priesnitz, Tim
Language: English
Year of Publication: 2003
OPUS Source: Information and Computation, v.186(2003), n.2, p.319-354
SWD key words: Logik des Entailment
Free key words: Automata Theory
DDC notations: 004 Computer science, internet
Publikation type: Journal Article
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-2562
Date of registration: 15-Jun-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
subtype.pdf307,02 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.