English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3824-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3825-4
Genre: Conference Paper

Files

show Files
hide Files
:
pods98.ps (Any fulltext), 248KB
 
File Permalink:
-
Name:
pods98.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Vorobyov, Sergei1, 2, Author           
Voronkov, Andrei2, Author           
Affiliations:
1Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2010-03-121998
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519675
Other: Local-ID: C1256104005ECAFC-64E8BC346A5A1603412566FA003D63DA-VorobyovVoronkov1998PODS
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Saeattle, Washington, U.S.A.
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-98)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 244 - 253 Identifier: ISBN: 0-89791-996-3