Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25769
Titel: First-order theory of subtyping constraints
Verfasser: Su, Zhendong
Aiken, Alexander
Niehren, Joachim
Priesnitz, Tim
Treinen, Ralf
Sprache: Englisch
Erscheinungsjahr: 2002
Quelle: The 29th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, Oregon, 16-18 January 2002, pp.203-216
SWD-Schlagwörter: Entscheidbarkeit ; Untertyp
Freie Schlagwörter: Subtyping Constraints
DDC-Sachgruppe: 004 Informatik
Dokumentart : InProceedings (Aufsatz / Paper einer Konferenz etc.)
Kurzfassung: We investigate the first-order theory of subtyping constraints. We show that the first-order theory of non-structural subtyping is undecidable, and we show that in the case where all constructors are either unary or nullary, the first-order theory is decidable for both structural and non-structural subtyping. The decidability results are shown by reduction to a decision problem on tree automata. This work is a step towards resolving long-standing open problems of the decidability of entailment for non-structural subtyping.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-2843
hdl:20.500.11880/25825
http://dx.doi.org/10.22028/D291-25769
SciDok-Publikation: 5-Jul-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fot02.pdf446,72 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.