Complexity of nonrecursive logic programs with complex values

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of nonrecursive logic programs with complex values

Full text

Pdf (1.33 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Seattle, Washington, United States

Pages: 244 - 253

Year of Publication: 1998

ISBN:0-89791-996-3

Authors

Sergei Vorobyov	Max-Planck Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany
Andrie Voronkov	Computing Science Department, Uppsala University, Box 311, S-75105, Uppsala, Sweden

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 20, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/275487.275515 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Catriel Beeri, The power of languages for the manipulation of complex values, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, p.727-794, October 1995 [doi>10.1007/BF01354881]
	2	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	3	Andrdka and N~meti. A generalized completeness of Horn clause logic seen as a programming language. Acta Oybernetica, 4:3-10, 1978.
	4	Krzysztof R. Apt, Logic programming, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	5	K,R, Apt and H.A. Blair. Arithmetic classification of perfect models of stratified programs. In R. Kowal- Bki and K,A. Bouwen, editors, Proceedings of the Fifth Joint International Conference and Symposium on Logic Programming (JICSLP-88), pages 766-779. The MIT Press, 1988.
	6	K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	7	K,R. Apt and R.N. Bol. Logic programming and negation: a survey, Journal of Logic Programming, 19,20:9- 71~ 1994,
	8	J, Barwise. Admissible Sets and Structures. Springer Verlag, 1975,
	9	Catriel Beeri , Shamim Naqvi , Oded Shmueli , Shalom Tsur, Set constructors in a logic database language, Journal of Logic Programming, v.10 n.3-4, p.181-232, April/May 1991 [doi>10.1016/0743-1066(91)90036-O]
	10	Michael Benedikt , Leonid Libkin, Languages for relational databases over interpreted structures, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.87-98, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263672]
	11	L, Berman. Precise bounds for Presburger arithmetic and the reals with addition: preliminary report. In International Conference of Foundations of Computer Science, pages 95-99, 1977.
	12	L. Berman. The complexity of logical theories. Theoretical Computer Science, 11:71-77, 1980.
	13	H. Blair, V.W. Marek, and J.S. Schlipf. The expressiveness of locally stratified programs. Annals of Mathematics and Artificial Intelligence, 15(3/4):209-229, 1995.
	14	A.R. Bruss and A. R. Meyer. On time-space classes and their relation to the theory of real addition. Theoretical Computer Science, 11:59--69, 1980.
	15	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	16	K.L. Clark. Negation as failure. In H. Gallaire and j. Minker, editors, Logic and Data Base, pages 293- 322. Plenum Press, New York, 1978.
	17	E. Dantsin. The complexity of Prolog without loops (in Russian). In Proceedings of the 4th Soviet Conference "Application of the Mathematical Logic Methods", volume 2, pages 112-113, Tallinn, 1986.
	18	Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and Expressive Power of Logic Programming, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.82, June 24-27, 1997
	19	E. Dantsin and A. Voronkov. Bag and set unification. UPMAIL Technical Report 150, Uppsala University, Computing Science Department, September 1997.
	20	E. Dantsin and A. Voronkov. Complexity of query answering in logic databases with complex data. UPMAIL Technical Report 149, Uppsala University, Computing Science Department, September 1997.
	21	Evgeny Dantsin , Andrei Voronkov, Complexity of Query Answering in Logic Databases with Complex Values, Proceedings of the 4th International Symposium on Logical Foundations of Computer Science, p.56-66, July 06-12, 1997
	22	A. Dovier, E.G. Omodeo, E. Pontelli, and G. Rossi. {log}: A language for programming in logic with finite sets. Journal of Logic Programming, 28(1):1-44, 1996.
	23	M. Falaschi , G. Levi , C. Palamidessi , M. Martelli, Declarative modeling of the operational behavior of logic languages, Theoretical Computer Science, v.69 n.3, p.289-318, Dec. 18, 1989 [doi>10.1016/0304-3975(89)90070-4]
	24	J. Ferrante and C. W. Rackoff. The computational complexity of logical theories, volume 718 of Lecture Notes in Mathematics. Springer-Verlag, 1979.
	25	Jean H. Gallier , Stan Raatz, Extending SLD resolution to equational horn clauses using E-unification, Journal of Logic Programming, v.6 n.1-2, p.3-43, Jan./Mar. 1989 [doi>10.1016/0743-1066(89)90028-9]
	26	L. Henkin. A theory of propositional types. Fundamenta Mathematicae, 52:323-344, 1963.
	27	W. Hodges. Model theory. Cambridge University Press, 1993.
	28	R. Hull , J. Su, Untyped sets, invention, and computable queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.347-359, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73755]
	29	Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Journal of Computer and System Sciences, v.43 n.1, p.219-267, Aug. 1991 [doi>10.1016/0022-0000(91)90036-5]
	30	Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
	31	Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
	32	David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	33	Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
	34	K, Kunen. Answer sets and negation as failure. In Sth International Conference on Logic Programming, volume 1, pages 219-228. The MIT Press, 1987.
	35	Kenneth Kunen, Negation in logic programming, Journal of Logic Programming, v.4 n.4, p.289-308, December 1, 1987 [doi>10.1016/0743-1066(87)90007-0]
	36	Gabriel M. Kuper , Moshe Y. Vardi, On the complexity of queries in the logical data model, Theoretical Computer Science, v.116 n.1, p.33-57, Aug. 2, 1993
	37	Gabriel M. Kuper, Logic programming with sets, Journal of Computer and System Sciences, v.41 n.1, p.44-64, August 1990 [doi>10.1016/0022-0000(90)90033-H]
	38	V. Lifschitz, On the declarative semantics of logic programs with negation, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	39	J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	40	M, Maher. Complete axiomatizations of the algebras of finite, rational and infinite trees. In Prec. IEEE Conference on Logic in Computer Science (LICS), pages 348-357, 1988.
	41	Michael J. Maher, A CLP View of Logic Programming, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.364-383, September 02-04, 1992
	42	Michael J. Maher, A logic programming view of CLP, Proceedings of the tenth international conference on logic programming on Logic programming, p.737-753, August 1993, Budapest, Hungary
	43	A, Maleev. Axiomatizable classes of locally free algebras of various types. In B.F. Wells III, editor, The Metamathematies of Algebraic Systems. Anatoli~ Ivanoui~ Mafeev. Collected Papers: 1936-1967, pages 262-281, North Holland, 1961.
	44	A, Mafeev. On the elementary theories of locally free universal algebras. Soviet Mathematical Doklady, 2(3);768-771, 1961.
	45	A,R. Meyer. The inherent computational complexity of theories of ordered sets. In International Congress of Mathematicians, pages 477--482, 1974.
	46	Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.12-19, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263664]
	47	T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	48	M. O. Rabin. A simple method for undeeidability proofs and some applications. In Y. Bar-Hillel, editor, Prec. Intern. Congress on Logic, Methodology and Philosophy of Science, Studies in Logic and the Foundations of Mathematics, pages 58-68, 1964.
	49	J.S. SchlipL Complexity and undeeidability results in logic programming. Annals of Mathematics and Artificial Intelligence, 15(3}4):257-288, 1995.
	50	Oded Shmueli , Shalom Tsur , Carlo Zaniolo, Compilation of set terms in the logic data language (LDL), Journal of Logic Programming, v.12 n.1-2, p.89-119, Jan. 1992 [doi>10.1016/0743-1066(92)90040-A]
	51	L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1-22, 1977.
	52	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
	53	S.-/~. T~nlund. Horn clause computability. BIT, 17:215-216, 1977.
	54	A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	55	Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
	56	Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]
	57	R. L. Vaught. Sentences true in all constructive models. Journal of Symbolic Logic, 25(1):39--53, 1960.
	58	H. Volger. A new hierarchy of elementary reeursive decision problems. Methods of Operations Research, 45:509-519, 1983.
	59	H. Volger. Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories (Note). Theoretical Computer Science, 23:333-337, 1983.
	60	Sergei G. Vorobyov, An Improved Lower Bound for the Elementary Theories of Trees, Proceedings of the 13th International Conference on Automated Deduction: Automated Deduction, p.275-287, August 03, 1996
	61	Sergei Vorobyov, The "Hardest'' Natural Decidable Theory, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, p.294, June 29-July 02, 1997
	62	S. Vorobyov and A. Voronkov. Complexity of nonrecursive logic programs with complex values. Technical Report MPI-I-97-2-010, Max-Planck institut f'dr Informatik, Saarbrficken, November 1997.

CITED BY 8

	Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
	A decision procedure for term algebras with queues, ACM Transactions on Computational Logic (TOCL), v.2 n.2, p.155-181, April 2001
	Evgeny Dantsin , Andrei Voronkov, Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.157-165, May 15-18, 2000, Dallas, Texas, United States
	Sergei Vorobyov, The most nonelementary theory, Information and Computation, v.190 n.2, p.196-219, 1 May 2004
	Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Christoph Koch, Query rewriting with symmetric constraints, AI Communications, v.17 n.2, p.41-55, April 2004
	Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1215-1256, December 2006
	Michael Benedikt , Leonid Libkin , Frank Neven, Logical definability and query languages over ranked and unranked trees, ACM Transactions on Computational Logic (TOCL), v.8 n.2, p.11-es, April 2007