ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS.
Saved in:
| Title: | ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS. |
|---|---|
| Authors: | Marcinkowski, Jerzy1 jma@tcs.uni.wroc.pl |
| Source: | SIAM Journal on Computing. 1999, Vol. 29 Issue 1, p231. 27p. |
| Subjects: | Logic programming languages, Query languages (Computer science), Decidability (Mathematical logic), Mathematical optimization |
| Abstract: | DATALOG is the language of logic programs without function symbols. It is considered to be the paradigmatic database query language. If it is possible to eliminate recursion from a DATALOG program then it is bounded. Since bounded programs can be executed in parallel constant time, the possibility of automatized boundedness detecting is believed to be an important issue and has been studied in many papers. Boundedness was proved to be undecidable for different kinds of semantical assumptions and syntactical restrictions. Many different proof techniques were used. In this paper we propose a uniform proof method based on the discovery of, as we call it, the Achilles-Turtle machine, and make strong improvements on most of the known undecidability results. In particular we solve the famous open problem of Kanellakis showing that uniform boundedness is undecidable for single rule programs (called also sirups). This paper is the full version of [J. Marcinkowski, Proc. 13th STACS, Lecture Notes in Computer Science 1046, pp. 427-438], and [J. Marcinkowski, 11th IEEE Symposium on Logic in Computer Science, pp. 13-24]. Key words: DATALOG; query optimization; decidability [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
