Complexity of Nonrecursive Logic Programs with Complex Values

Vorobyov, Sergei; Voronkov, Andrei

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Complexity of Nonrecursive Logic Programs with Complex Values

MPS-Authors

/persons/resource/persons45677

Vorobyov, Sergei
Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society;
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45678

Voronkov, Andrei
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-3824-6

要旨

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.