Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Bericht

Satisfiability of Functional+Record Subtype Constraints is NP-Hard

MPG-Autoren
/persons/resource/persons45677

Vorobyov,  Sergei
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

MPI-I-98-2-004.pdf
(beliebiger Volltext), 254KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Vorobyov, S.(1998). Satisfiability of Functional+Record Subtype Constraints is NP-Hard (MPI-I-1998-2-004). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-7B51-7
Zusammenfassung
We show the NP-hardness of the satisfiability problem for subtype inequalities between object types built by using simultaneously both the functional and the record type constructors, without base types. Earlier research concentrated on the complexity of subtyping either solely functional, or solely record types. In both cases deterministic cubic time algorithms are known.