Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Complexity of Nonrecursive Logic Programs with Complex Values

Vorobyov, S., & Voronkov, A. (1998). Complexity of Nonrecursive Logic Programs with Complex Values. In Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-98) (pp. 244-253). New York, USA: ACM.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3824-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3825-4
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
pods98.ps (beliebiger Volltext), 248KB
 
Datei-Permalink:
-
Name:
pods98.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           
Voronkov, Andrei2, 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: We investigate complexity of the $\success$ problem for logic query languages with complex values: check whether a query defines a nonempty set. The $\success$ problem for recursive query languages with complex values is undecidable, so we study the complexity of nonrecursive queries. By complex values we understand values such as trees, finite sets, and multisets. Due to the well-known correspondence between relational query languages and datalog, our results can be considered as results about relational query languages with complex values. The paper gives a complete complexity classification of the $\success$ problem for nonrecursive logic programs over trees depending on the underlying signature, presence of negation, and range restrictedness. We also prove several results about finite sets and multisets.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121998
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : ACM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519675
Anderer: Local-ID: C1256104005ECAFC-64E8BC346A5A1603412566FA003D63DA-VorobyovVoronkov1998PODS
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Saeattle, Washington, U.S.A.
Start-/Enddatum: -

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-98)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 244 - 253 Identifikator: ISBN: 0-89791-996-3