Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Subtyping Functional+Nonempty Record Types

Vorobyov, S. (1999). Subtyping Functional+Nonempty Record Types. In G. Gottlob, E. Grandjean, & K. Seyr (Eds.), Proceedings of the 12th International Workshop on Computer Science Logic (CSL-98), Annual Conference on the EACSL (pp. 285-297). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3699-E Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-369B-A
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
csl98-final.ps (beliebiger Volltext), 197KB
 
Datei-Permalink:
-
Name:
csl98-final.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Vorobyov, Sergei1, 2, Autor           
Affiliations:
1Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: \begin{abstract} \emph{Solving systems of subtype constraints} (or \emph{subtype inequalities}) is in the core of efficient \emph{type reconstruction} in modern object-oriented languages with subtyping and inheritance, two problems known \emph{polynomial time equivalent}. It is important to know how different combinations of type constructors influence the complexity of the problem. We show the \emph{NP-hardness} of the satisfiability problem for subtype inequalities between object types built by using simultaneously both the functional and the non-empty record type constructors, but without any atomic types and atomic subtyping. The class of constraints we address is intermediate with respect to known classes. For pure functional types with atomic subtyping of a special non-lattice (\emph{crown}) form solving subtype constraints is PSPACE-complete \cite{Tiuryn92,Frey97}. On the other hand, if there are no atomic types and subtyping on them, but the largest $\top$ type is included, then both pure functional and pure record (separately) subtype constraints are \emph{polynomial time solvable} \cite{KozenPalsbergSchwartzbach94,Palsberg95ic}, which is mainly due to the lattice type structure. We show that combining the functional and nonempty record constructors yields NP-hardness \emph{without any atomic subtyping}, and the same is true for just a single type constant with a nonempty record constructor. \end{abstract}

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519677
Anderer: Local-ID: C1256104005ECAFC-B535BC26FE7E2720412566FA003F0BE5-Vorobyov1998CSL
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Brno, Czech Republic
Start-/Enddatum: 1999

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 12th International Workshop on Computer Science Logic (CSL-98), Annual Conference on the EACSL
Genre der Quelle: Konferenzband
 Urheber:
Gottlob, Georg, Herausgeber
Grandjean, Etienne, Herausgeber
Seyr, Katrin, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 285 - 297 Identifikator: ISBN: 3-540-65922-6

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1584 Artikelnummer: - Start- / Endseite: - Identifikator: -