Complexity and expressive power of logic programming

ABSTRACT

This article surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and datalog, but we also mention general logic programming with function symbols. Next to classical results on plain logic programming (pure Horn clause programs), more recent results on various important extensions of logic programming are surveyed. These include logic programming with different forms of negation, disjunctive logic programming, logic programming with equality, and constraint logic programming.

REFERENCES

• 1: AANDERAA,S.AND B~RGER, E. 1979. The Horn complexity of Boolean functions and Cook's problem. In B. Mayoh and F. Jensen, Eds., Proceedings 5th Scandinavian Logic Symposium, pp. 231-256. Aalborg, Denmark: Aalborg University Press.
• 2: Serge Abiteboul, Boundedness is undecidable for datalog programs with a single recursive rule, Information Processing Letters, v.32 n.6, p.281-287, Oct. 3, 1989 [doi>10.1016/0020-0190(89)90019-7]
• 3: 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]
• 4: Serge Abiteboul , Stéphane Grumbach, COL: A Logic-Based Language for Complex Objects, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.271-293, March 14-18, 1988
• 5: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Journal of the ACM (JACM), v.45 n.5, p.798-842, Sept. 1998 [doi>10.1145/290179.290182]
• 6: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Journal of the ACM (JACM), v.45 n.5, p.798-842, Sept. 1998 [doi>10.1145/290179.290182]
• 7: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 8: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 9: Serge Abiteboul , Victor Vianu, Computing with first-order logic, Journal of Computer and System Sciences, v.50 n.2, p.309-335, April 1995
• 10: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 11: Serge Abiteboul , Moshe Y. Vardi , Victor Vianu, Fixpoint logics, relational machines, and computational complexity, Journal of the ACM (JACM), v.44 n.1, p.30-56, Jan. 1997 [doi>10.1145/256292.256295]
• 12: Foto N. Afrati, Bounded arity Datalog ( ≠ ) queries on graphs, Journal of Computer and System Sciences, v.55 n.2, p.210-228, Oct. 1997 [doi>10.1006/jcss.1997.1521]
• 13: F. Afrati , S. S. Cosmadakis, Expressiveness of restricted recursive queries, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.113-126, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73018]
• 14: Foto Afrati , Christos H. Papadimitriou, The parallel complexity of simple logic programs, Journal of the ACM (JACM), v.40 n.4, p.891-916, Sept. 1993 [doi>10.1145/153724.153752]
• 15: Foto Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis, On Datalog vs. polynomial time, Journal of Computer and System Sciences, v.51 n.2, p.177-196, Oct. 1995 [doi>10.1006/jcss.1995.1060]
• 16: Miklos Ajtai , Yuri Gurevich, Datalog vs. first-order logic, Journal of Computer and System Sciences, v.49 n.3, p.562-588, Dec. 1994
• 17: ANDR~KA,H.AND N~METI, I. 1978. The generalized completeness of Horn predicate logic as a programming language. Acta Cybernetica 4, 3-10. (This is the published version of a 1975 report entitled "General Completeness of PROLOG".)
• 18: Krzysztof R. Apt, Logic programming, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 19: APT,K.R.AND BLAIR, H. A. 1988. Arithmetic classification of perfect models of stratified programs. In R. A. Kowalski and K. A. Bowen, Eds., Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (ICLP/SLP 1988) (Aug. 1988), pp. 765-779. The MIT Press.
• 20: APT,K.R.AND BOL, R. N. 1994. Logic programming and negation: A survey. Journal of Logic Programming 19/20, 9-71.
• 21: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• 22: 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
• 23: Franz Baader , Klaus U. Schulz, Unification in the Union of Disjoint Equational Theories: Combining Decision Procedures, Proceedings of the 11th International Conference on Automated Deduction: Automated Deduction, p.50-65, June 15-18, 1992
• 24: Franz Baader , Klaus U. Schulz, Unification in the union of disjoint equational theories: combining decision procedures, Journal of Symbolic Computation, v.21 n.2, p.211-243, Feb. 1996 [doi>10.1006/jsco.1996.0009]
• 25: Franz Baader , Jörg H. Siekmann, Unification theory, Handbook of logic in artificial intelligence and logic programming, Oxford University Press, Inc., New York, NY, 1994
• 26: Leo Bachmair , Ta Chen , C. R. Ramakrishnan , I. V. Ramakrishnan, Subsumption Algorithms Based on Search Trees, Proceedings of the 21st International Colloquium on Trees in Algebra and Programming, p.135-148, April 22-24, 1996
• 27: José Luis Balcázar , Joseph Díaz , Joaquim Gabarró, Structural complexity 2, Springer-Verlag New York, Inc., New York, NY, 1990
• 28: José L. Balcázar , Antoni Lozano , Jacobo Torán, The complexity of algorithmic problems on succinct instances, Computer science: research and applications, Plenum Press, New York, NY, 1992
• 29: BARAL,C.AND GELFOND, M. 1994. Logic programming and knowledge representation. Journal of Logic Programming 19/20, 73-148.
• 30: BARAL,C.AND SUBRAHMANIAN, V. 1993. Dualities between alternative semantics for logic programming and nonmonotonic reasoning. Journal of Automated Reasoning 10, 3 (June), 399-420.
• 31: BEN-ELIYAHU,R.AND DECHTER, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, I-II, 53-87.
• 32: Dan Benanav , Deepak Kapur , Paliath Narendran, Complexity of matching problems, Journal of Symbolic Computation, v.3 n.1-2, p.203-216, Feb./April 1987 [doi>10.1016/S0747-7171(87)80027-5]
• 33: Michael Benedikt , Leonid Libkin, On the Structure of Queries in Constraint Query Languages, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.25, July 27-30, 1996
• 34: 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]
• 35: Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong, Relational expressive power of constraint query languages, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.5-16, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237667]
• 36: Kenneth A. Berman , John S. Schlipf , John V. Franco, Computing Well-founded Semantics Faster, Proceedings of the Third International Conference on Logic Programming and Nonmonotonic Reasoning, p.113-126, June 26-28, 1995
• 37: BERMAN, L. 1977. Precise bounds for Presburger arithmetic and the reals with addition: Preliminary report. In 18th Annual Symposium on Foundations of Computer Science (FOCS '77) (Providence, Rhode Island, Oct./Nov. 1977), pp. 95-99. IEEE.
• 38: BERMAN, L. 1980. The complexity of logical theories. Theoretical Computer Science 11, 71-77.
• 39: Nicole Bidoit, Negation in rule-based database languages: a survey, Theoretical Computer Science, v.78 n.1, p.3-83, Jan. 21, 1991
• 40: Nicole Bidoit , Christine Froidevaux, Negation by default and unstratifiable logic programs, Theoretical Computer Science, v.78 n.1, p.85-112, Jan. 21, 1991
• 41: BLAIR, H. A. 1982. The recursion-theoretical complexity of the semantics of predicate logic as a programming language. Information and Control 54, 1/2 (Jan.), 25-47.
• 42: Piero A. Bonatti , Thomas Eiter, Querying disjunctive databases through nonmonotonic logics, Theoretical Computer Science, v.160 n.1-2, p.321-363, June 10, 1996 [doi>10.1016/0304-3975(95)00192-1]
• 43: Anthony J. Bonner, Hypothetical datalog: complexity and expressibility, Theoretical Computer Science, v.76 n.1, p.3-51, Oct. 31, 1990 [doi>10.1016/0304-3975(90)90011-6]
• 44: BONNER, A. J. 1997. Intuitionistic deductive databases and the polynomial time hierarchy. Journal of Logic Programming 33, 1 (Oct.), 1-47.
• 45: B~RGER, E. 1971. Reduktionstypen in Kromund Hornformeln. PhD thesis, Fachbereich Mathematik der Universit~t M~nster.
• 46: B~ORGER, E. 1974. Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen. Archiv f~r mathematische Logik und Grudlagenforschung 16, 1-2, 67-84.
• 47: B~RGER, E. 1984. Decision problems in predicate logic. In G. Lolli, G. Longo, and A. Marcja, Eds., Logic Colloquium '82, Volume 112 of Studies in Logic and the Foundations of Mathematics (1984), pp. 263-301. North Holland.
• 48: B~RGER, E., GR~DEL, E., AND GUREVICH, Y. 1997. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer-Verlag, Berlin.
• 49: BRASS,S.AND DIX, J. 1995. Disjunctive semantics based upon partial and bottom-up evaluation. In L. Sterling, Ed., Logic Programming, Proceedings of the Twelfth International Conference on Logic Programming, June 13-16, 1995, Tokyo, Japan (ICLP '95) (June 1995), pp. 199-213. MIT Press.
• 50: Gerhard Brewka , Thomas Eiter, Preferred answer sets for extended logic programs, Artificial Intelligence, v.109 n.1-2, p.297-356, April 1999 [doi>10.1016/S0004-3702(99)00015-6]
• 51: Gerhard Brewka , Thomas Eiter, Preferred answer sets for extended logic programs, Artificial Intelligence, v.109 n.1-2, p.297-356, April 1999 [doi>10.1016/S0004-3702(99)00015-6]
• 52: Francesco Buccafurri , Sergio Greco , Domenico Saccà, The Expressive Power of Unique Total Stable Model Semantics, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.849-859, July 07-11, 1997
• 53: Francesco Buccafurri , Nicola Leone , Pasquale Rullo, Strong and Weak Constraints in Disjunctive Datalog, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, p.2-17, July 28-31, 1997
• 54: BUCCAFURRI, F., LEONE,N.,AND RULLO, P. 1998. Disjunctive ordered logic: Semantics and expressiveness. In A. G. Cohn, L. Schubert, and S. C. Shapiro, Eds., Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR '98), Trento, Italy, June 2-5, 1998 (June 1998), pp. 418-431. Morgan Kaufmann. Full paper: {Buccafurri et al. 1999}.
• 55: Francesco Buccafurri , Nicola Leone , Pasquale Rullo, Semantics and expressiveness of disjunctive ordered logic, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.311-337, 1999 [doi>10.1023/A:1018986207453]
• 56: Francesco Buccafurri , Nicola Leone , Pasquale Rullo, Enhancing Disjunctive Datalog by Constraints, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.845-860, September 2000 [doi>10.1109/69.877512]
• 57: B~CHI, J. 1962. Turing machines and the Entscheidungsproblem. Mathematische Annalen 148, 201-213.
• 58: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 59: Marco Cadoli , Luigi Palopoli, Circumscribing DATALOG: expressive power and complexity, Theoretical Computer Science, v.193 n.1-2, p.215-244, Feb. 28, 1998 [doi>10.1016/S0304-3975(97)00108-4]
• 60: CADOLI,M.AND SCHAERF, M. 1993. A survey of complexity results for nonmonotonic logics. Journal of Logic Programming 17, 2/3&4 (Nov.), 127- 160.
• 61: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 62: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 63: E. P. F. Chan, A Possible World Semantics for Disjunctive Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.282-292, April 1993 [doi>10.1109/69.219736]
• 64: CHANDRA,A.K.AND HAREL, D. 1982. Structure and complexity of relational queries. Journal of Computer and System Sciences 25, 1 (Aug.), 99-128.
• 65: CHANDRA,A.K.AND HAREL, D. 1985. Horn clause queries and generalizations. Journal of Logic Programming 2, 1 (April), 1-15.
• 66: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 67: 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]
• 68: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• 69: Surajit Chaudhuri , Moshe Y. Vardi, On the complexity of equivalence between recursive and nonrecursive Datalog programs, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.107-116, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182604]
• 70: CHAUDHURI,S.AND VARDI, M. Y. 1997. On the equivalence of recursive and nonrecursive datalog programs. Journal of Computer and System Sciences 54, 1 (Feb.), 61-78.
• 71: CHOLAK,P.AND BLAIR, H. A. 1994. The complexity of local stratification. Fundamenta Informaticae 21, 4 (Oct.), 333-344.
• 72: J. Chomicki , V. S. Subrahmanian, Generalized closed world assumption is II-complete, Information Processing Letters, v.34 n.6, p.289-291, May 1990 [doi>10.1016/0020-0190(90)90012-M]
• 73: Latha S. Colby , Leonid Libkin, Tractable Iteration Mechanisms for Bag Languages, Proceedings of the 6th International Conference on Database Theory, p.461-475, January 08-10, 1997
• 74: COLMERAUER, A., KANOUI, H., ROUSSEL,P.,AND PASSERO, R. 1973. Un syst~me de communication homme-machine en Francais. Technical report, Groupe de Recherche en Intelligence Artificielle, Universit~ d'Aix-Marseille II.
• 75: CORCIULO, L., GIANNOTTI,F.,AND PEDRESCHI, D. 1993. Datalog with non-deterministic choice computes NDB-PTIME. In S. Ceri, K. Tanaka, and S. Tsur, Eds., Deductive and Object- Oriented Databases, Third International Conference, DOOD '93, Phoenix, Arizona, USA, December 6-8, 1993, Proceedings, Volume 760 of Lecture Notes in Computer Science (Dec. 1993), pp. 49-66. Springer-Verlag.
• 76: S. S. Cosmadakis, On the first-order expressibility of recursive queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.311-323, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73752]
• 77: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• 78: COSMADAKIS,S.S.AND KUPER, G. M. 1994. Expressiveness of first-order constraint languages. Technical Report ECRC-94-13, European Computer Industry Research Center.
• 79: Jim Cox , Ken McAloon, Decision procedure for constraint based extensions of Datalog, Constraint logic programming: selected research, MIT Press, Cambridge, MA, 1993
• 80: Jim Cox , Ken McAloon , Carol Tretkoff, Computational complexity and constraint logic programming languages, Proceedings of the 1990 North American conference on Logic programming, p.401-415, January 1990, Austin, Texas, United States
• 81: Elias Dahlhaus, Skolem normal forms concerning the least fixpoint, Computation theory and logic, Springer-Verlag, London, 1987
• 82: 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
• 83: Evgeny Dantsin , Andrei Voronkov, A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees, Proceedings of the Second International Conference on Foundations of Software Science and Computation Structure, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.180-196, March 22-28, 1999
• 84: 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 [doi>10.1145/335168.335218]
• 85: 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
• 86: DAVIS, M., ED. 1965. The Undecidable: Basic Papers on Undecidable, Unsolvable Problems and Computable Functions. Raven Press, New York.
• 87: DEGTYAREV,A.AND VORONKOV, A. 1996. A note on semantics of logics programs with equality based on complete sets of E-unifiers. Journal of Logic Programming 28, 3 (Sept.), 207-216.
• 88: P. Devienne, Weighted graphs: a tool for studying the halting problem and time complexity in term rewriting systems and logic programming, Theoretical Computer Science, v.75 n.1-2, p.157-215, Sep. 1990 [doi>10.1016/0304-3975(90)90066-Q]
• 89: DEVIENNE, P., LEB~GUE, P., PARRAIN, A., ROUTIER, J.-C., AND W~RTZ, J. 1996. Smallest Horn clause programs. Journal of Logic Programming 27, 3 (June), 227-267.
• 90: Philippe Devienne , Patrick Lebègue , Jean-Christophe Routier, Halting Problem of One Binary Horn Clause is Undecidable, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.48-57, February 25-27, 1993
• 91: A. Ja. Dikovsky, On computational complexity of Prolog programs, Theoretical Computer Science, v.119 n.1, p.63-102, Oct. 11, 1993
• 92: Jürgen Dix , Georg Gottlob , Wiktor Marek, Reducing disjunctive to non-disjunctive semantics by shift-operations, Fundamenta Informaticae, v.28 n.1-2, p.87-100, Nov. 1996
• 93: Guozhu Dong , Leonid Libkin , Limsoon Wong, Local Properties of Query Languages, Proceedings of the 6th International Conference on Database Theory, p.140-154, January 08-10, 1997
• 94: DOWLING,W.F.AND GALLIER, J. H. 1984. Lineartime algorithms for testing the satisfiability of propositional Horn theories. Journal of Logic Programming 1, 3 (Oct.), 267-284.
• 95: Sergey M. Dudakov, On the complexity of perfect models of logic programs, Fundamenta Informaticae, v.39 n.3, p.249-258, Aug. 1999
• 96: Cynthia Dwork , Paris C. Kanellakis , John C. Mitchell, On the sequential nature of unification, Journal of Logic Programming, v.1 n.1, p.35-50, June 1984 [doi>10.1016/0743-1066(84)90022-0]
• 97: Cynthia Dwork , Paris C. Kanellakis , Larry Stockmeyer, Parallel algorithms for term matching, SIAM Journal on Computing, v.17 n.4, p.711-731, August 1988 [doi>10.1137/0217046]
• 98: EBBINGHAUS, H.-D. AND FLUM, J. 1995. Finite Model Theory. Perspectives in Mathematical Logic. Springer-Verlag.
• 99: Thomas Eiter , Georg Gottlob, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Artificial Intelligence, v.57 n.2-3, p.227-270, Oct. 1992 [doi>10.1016/0004-3702(92)90018-S]
• 100: Thomas Eiter , Georg Gottlob, Propositional circumscription and extended closed-world reasoning are &Pgr;p2-complete, Theoretical Computer Science, v.114 n.2, p.231-245, June 21, 1993 [doi>10.1016/0304-3975(93)90073-3]
• 101: Thomas Eiter , Georg Gottlob, The complexity of logic-based abduction, Journal of the ACM (JACM), v.42 n.1, p.3-42, Jan. 1995 [doi>10.1145/200836.200838]
• 102: EITER,T.AND GOTTLOB, G. 1995b. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3-4, 289-323.
• 103: EITER,T.AND GOTTLOB, G. 1997. Expressiveness of stable model semantics for disjunctive logic programs with functions. Journal of Logic Programming 33, 2 (Nov.), 167-178.
• 104: Thomas Eiter , Georg Gottlob , Nicola Leone, Abduction from logic program: semantics and complexity, Theoretical Computer Science, v.189 n.1-2, p.129-177, Dec. 15, 1997 [doi>10.1016/S0304-3975(96)00179-X]
• 105: EITER, T., GOTTLOB,G.,AND LEONE, N. 1997b. On the indiscernibility of individuals in logic programming. Journal of Logic and Computation 7,6 (Dec.), 805-824.
• 106: Thomas Eiter , Georg Gottlob , Heikki Mannila, Adding disjunction to datalog (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.267-278, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182639]
• 107: Thomas Eiter , Georg Gottlob , Heikki Mannila, Disjunctive datalog, ACM Transactions on Database Systems (TODS), v.22 n.3, p.364-418, Sept. 1997 [doi>10.1145/261124.261126]
• 108: Thomas Eiter , Georg Gottlob , Helmut Veith, Modular Logic Programming and Generalized Quantifiers, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, p.290-309, July 28-31, 1997
• 109: Thomas Eiter , Georg Gottlob , Helmut Veith, Generalized Quantifiers in Logic Programs, Revised Lectures from the 9th European Summer School on Logic, Language, and Information: Generalized Quantifiers and Computation, p.72-98, August 11-22, 1997
• 110: Thomas Eiter , Nicola Leone , Domenico Saccá, Expressive power and complexity of partial models for disjunctive deductive databases, Theoretical Computer Science, v.206 n.1-2, p.181-218, Oct. 6, 1998 [doi>10.1016/S0304-3975(97)00129-1]
• 111: Thomas Eiter , James Lu , V. S. Subrahmanian, A first-order representation of stable models, AI Communications, v.11 n.1, p.53-73, Sept. 1997
• 112: FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, Ed., Complexity of Computation (1974), pp. 43-74. American Mathematical Society.
• 113: 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]
• 114: Melvin Fitting, Computability theory, semantics, and logic programming, Oxford University Press, Inc., New York, NY, 1987
• 115: Melvin Fitting, Enumeration operators and modular logic programming, Journal of Logic Programming, v.4 n.1, p.11-21, March 1987 [doi>10.1016/0743-1066(87)90019-7]
• 116: Jörg Flum , Max Kubierschky , Bertram Ludäscher, Total and Partial Well-Founded Datalog Coincide, Proceedings of the 6th International Conference on Database Theory, p.113-124, January 08-10, 1997
• 117: GAIFMAN, H., MAIRSON, H. G., SAGIV,Y.,AND VARDI,M.Y. 1987. Undecidable optimization problems for database logic programs. In Proceedings of the Symposium on Logic in Computer Science (LICS '87), Ithaca, New York, USA, June 22-25, 1987 (June 1987), pp. 106-115. IEEE Computer Society Press.
• 118: GALLIER,J.H.AND RAATZ, S. 1986. SLD- resolution methods for Horn clauses with equality based on E-unification. In Proceedings of the 1986 Symposium on Logic Programming, Salt Lake City, Utah, September 22-25, 1986 (SLP '86) (Sept. 1986), pp. 168-179.
• 119: 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]
• 120: GAREY,M.R.AND JOHNSON, D. S. 1979. Computers and Intractability. Freeman, San Francisco.
• 121: GELFOND,M.AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In R. A. Kowalski and K. A. Bowen, Eds., Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (ICLP/SLP 1988) (Aug. 1988), pp. 1070-1080. The MIT Press.
• 122: GELFOND,M.AND LIFSCHITZ, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3-4, 365-386.
• 123: GIANNOTTI,F.AND PEDRESCHI, D. 1998. Datalog with non-deterministic choice computes NDB-PTIME. Journal of Logic Programming 35,1 (April), 79-110.
• 124: Fosca Giannotti , Sergio Greco , Domenico Saccà , Carlo Zaniolo, Programming with non-determinism in deductive databases, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.97-125, 1997 [doi>10.1023/A:1018999404360]
• 125: GIVAN,R.AND MCALLESTER, D. 2000. Polynomialtime computation via local inference relations. submitted.
• 126: Georg Gottlob, Subsumption and implication, Information Processing Letters, v.24 n.2, p.109-111, January 1987 [doi>10.1016/0020-0190(87)90103-7]
• 127: GOTTLOB, G. 1992. Complexity results for nonmonotonic logics. Journal of Logic and Computation 2, 3 (June), 397--425.
• 128: Georg Gottlob , Christian G. Fermüller, Removing redundancy from a clause, Artificial Intelligence, v.61 n.2, p.263-289, June 1993 [doi>10.1016/0004-3702(93)90069-N]
• 129: Georg Gottlob , Alexander Leitsch, Fast Subsumption Algorithms, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.64-77, April 01-03, 1985
• 130: G. Gottlob , A. Leitsch, On the efficiency of subsumption algorithms, Journal of the ACM (JACM), v.32 n.2, p.280-295, April 1985 [doi>10.1145/3149.214118]
• 131: Georg Gottlob , Christos H. Papadimitriou, On the Complexity of Single-Rule Datalog Queries, Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.201-222, September 06-10, 1999
• 132: Georg Gottlob , Reinhard Pichler, Working with Arms: Complexity Results on Atomic Representations of Herbrand Models, Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, p.306, July 02-05, 1999
• 133: GOTTLOB, G., GRADEL, E., AND VEITH, H. 2000a. Datalog LITE: A deductive query language with linear time model checking. Manuscript, submitted for publication.
• 134: Georg Gottlob , Erich Grädel , Helmut Veith, linear time datalob and branching time logic, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2001
• 135: Georg Gottlob , Nicola Leone , Francesco Scarcello, On the Complexity of Some Inductive Logic Programming Problems, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.17-32, September 17-20, 1997
• 136: Georg Gottlob , Nicola Leone , Francesco Scarcello, The Complexity of Acyclic Conjunctive Queries, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.706, November 08-11, 1998
• 137: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303979]
• 138: Georg Gottlob , Nicola Leone , Francesco Scarcello, On the complexity of some inductive logic programming problems, New Generation Computing, v.17 n.1, p.53-75, Jan. 1999 [doi>10.1007/BF03037582]
• 139: Georg Gottlob , Nicola Leone , Helmut Veith, Second Order Logic and the Weak Exponential Hierarchies, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.66-81, August 28-September 01, 1995
• 140: GOTTLOB, G., LEONE,N.,AND VEITH, H. 1999c. Succinctness as a source of complexity in logical formalisms. Annals of Pure and Applied Logic 97, 1-3 (March), 231-260.
• 141: Georg Gottlob , Sherry Marcus , Anil Nerode , Gernot Salzer , V. S. Subrahmanian, A non-ground realization of the stable and well-founded semantics, Theoretical Computer Science, v.166 n.1-2, p.221-262, Oct. 20, 1996 [doi>10.1016/0304-3975(95)00207-3]
• 142: Erich Grädel, Capturing complexity classes by fragments of second-order logic, Theoretical Computer Science, v.101 n.1, p.35-57, July 13, 1992 [doi>10.1016/0304-3975(92)90149-A]
• 143: Sergio Greco , Domenico Saccà, The Expressive Power of "Possible-is-Certain" Semantics (Extended Abstract), Proceedings of the Second Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, p.33-42, December 02-05, 1996
• 144: Sergio Greco , Domenico Saccà, Deterministic Semantics for Datalog¬: Complexity and Expressive Power, Proceedings of the 5th International Conference on Deductive and Object-Oriented Databases, p.337-350, December 08-12, 1997
• 145: Sergio Greco , Luigi Palopoli , Eugenio Spadafora, Extending Datalog with arrays, Data & Knowledge Engineering, v.17 n.1, p.31-57, Oct. 1995 [doi>10.1016/0169-023X(95)00027-P]
• 146: Claude Cordell Green, The application of theorem proving to question-answering systems, 1969
• 147: D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
• 148: Stéphane Grumbach , Zoé Lacroix, On non-determinism in machines and languages, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.169-213, 1997 [doi>10.1023/A:1018955722107]
• 149: Stéphane Grumbach , Jianwen Su, First-order Definability over Constraint Databases, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.121-136, September 19-22, 1995
• 150: Stéphane Grumbach , Victor Vianu, Tractable query languages for complex object databases, Journal of Computer and System Sciences, v.51 n.2, p.149-167, Oct. 1995 [doi>10.1006/jcss.1995.1058]
• 151: Stéphane Grumbach , Jianwen Su , Christophe Tollu, Linear Constraint Query Languages: Expressive Power and Complexity, Selected Papers from the International Workshop on Logical and Computational Complexity, p.426-446, October 13-16, 1994
• 152: GUREVICH, Y. 1988. Logic and the challenge of computer science. In E. Borger, Ed., Current Trends in Theoretical Computer Science, Chapter 1, pp. 1-57. Computer Science Press.
• 153: GUREVICH,Y.AND SHELAH, S. 1986. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic 32, 265-280.
• 154: Marc Gyssens , Dan Suciu , Dirk Van Gucht, The Restricted and Bounded Fixpoint Closures of the Nested Relational Algebra are Equivalent, Proceedings of the Fifth International Workshop on Database Programming Languages, p.5, September 06-08, 1995
• 155: Philipp Hanschke , Jörg Würtz, Satisfiability of the smallest binary program, Information Processing Letters, v.45 n.5, p.237-241, April 2, 1993 [doi>10.1016/0020-0190(93)90210-Z]
• 156: HANUS, M. 1994. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming 19/20, 583- 628.
• 157: HERBRAND, J. 1972. Logical Writings. Harvard University Press.
• 158: HILLEBRAND,G.G.,KANELLAKIS,P.C.,MAIRSON,H.G., AND VARDI, M. Y. 1995. Undecidable boundedness problems for datalog programs. Journal of Logic Programming 25, 2 (Nov.), 163-190.
• 159: H~BLER, S. 1989. Foundations of Equational Logic Programming, Volume 353 of Lecture Notes in Artificial Intelligence. Springer- Verlag.
• 160: Richard Hull , Jianwen Su, Domain independence and the relational calculus, Acta Informatica, v.31 n.6, p.513-524, Sept. 1994 [doi>10.1007/BF01213204]
• 161: D. Ierardi, Quantifier elimination in the theory of an algebraically-closed field, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.138-147, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73020]
• 162: 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]
• 163: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• 164: IMMERMAN, N. 1999. Descriptive Complexity. Graduate Texts in Computer Science. Springer- Verlag, new York.
• 165: Katsumi Inoue , Chiaki Sakama, Transforming abductive logic programs to disjunctive programs, Proceedings of the tenth international conference on logic programming on Logic programming, p.335-353, August 1993, Budapest, Hungary
• 166: INOUE,K.AND SAKAMA, C. 1998. Negation as failure in the head. Journal of Logic Programming 35,1 (April), 39-78.
• 167: IOANNIDIS, Y. E. 1986. A time bound on the materialization of some recursively defined views. Algorithmica 1, 3, 361-385.
• 168: A. Itai , J. A. Makowshy, Unification as a complexity measure for logic programming, Journal of Logic Programming, v.4 n.2, p.105-117, June 1, 19876 [doi>10.1016/0743-1066(87)90014-8]
• 169: JAFFAR,J.AND MAHER, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503-581.
• 170: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 171: JONES,N.D.AND LAASER, W. T. 1976. Complete problems for deterministic polynomial time. Theoretical Computer Science 3, 1, 105-117.
• 172: P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 173: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 174: Paris C. Kanellakis , Dina Q. Goldin, Constraint Programming and Database Query Languages, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.96-120, April 19-22, 1994
• 175: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• 176: 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
• 177: D Kapur , P Narendran, NP-completeness of the set unification and matching problems, Proc. of the 8th international conference on Automated deduction, p.489-495, August 1986, Oxford, United Kingdom
• 178: Deepak Kapur , Paliath Narendran, Complexity of unification problems with associative-commutative operators, Journal of Automated Reasoning, v.9 n.2, p.261-288, Oct. 1992 [doi>10.1007/BF00245463]
• 179: Jörg-Uwe Kietz , Sašo Džeroski, Inductive logic programming and learnability, ACM SIGART Bulletin, v.5 n.1, p.22-32, Jan. 1994 [doi>10.1145/181668.181674]
• 180: Michael Kifer , James Wu, A logic for programming with complex objects, Journal of Computer and System Sciences, v.47 n.1, p.77-120, Aug. 1993
• 181: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 182: Phokion G. Kolaitis, The expressive power of stratified logic programs, Information and Computation, v.90 n.1, p.50-66, Jan. 1991 [doi>10.1016/0890-5401(91)90059-B]
• 183: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Journal of Computer and System Sciences, v.43 n.1, p.125-144, Aug. 1991 [doi>10.1016/0022-0000(91)90033-2]
• 184: KOLAITIS,P.G.AND VARDI, M. Y. 1992. Fixpoint logic vs. infinitary logic in finite-model theory. In Proceedings, Seventh Annual IEEE Symposium on Logic in Computer Science (LICS '92) (Santa Cruz, California, 22-25 June 1992), pp. 46-57. IEEE Computer Society Press.
• 185: Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, v.51 n.1, p.110-134, Aug. 1995
• 186: Antoni Kościelski , Leszek Pacholski, Complexity of Makanin's algorithm, Journal of the ACM (JACM), v.43 n.4, p.670-684, July 1996 [doi>10.1145/234533.234543]
• 187: KOWALSKI, R. A. 1974. Predicate logic as programming language. In J. L. Rosenfeld, Ed., Information Processing 74, Proceedings of IFIP Congress 74, Stockholm, Sweden, August 5-10, 1974 (IFIP '74) (Amsterdam, Aug. 1974), pp. 569-574. North Holland.
• 188: KOWALSKI,R.A.AND KUEHNER, D. 1971. Linear resolution with selection function. Artificial Intelligence 2, 3/4, 227--260.
• 189: V. S. Lakshmanan , A. O. Mendelzon, Inductive pebble games and the expressive power of datalog, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.301-310, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73751]
• 190: Alexander Leitsch, Deciding Horn classes by hyperresolution, Proceedings of the third workshop on Computer science logic, p.225-241, July 1990, Kaiserslautern, Germany
• 191: Alexander Leitsch, The resolution calculus, Springer-Verlag New York, Inc., New York, NY, 1997
• 192: LEITSCH,A.AND GOTTLOB, G. 1990. Deciding Horn clause implication problems by ordered semantic resolution. In F. Gardin and G. Mauri, Eds., Computational Intelligence II, Proceedings of the International Symposium, Milan, Italy, 25- 27 Sept. 1989 (Amsterdam, The Netherlands, 1990), pp. 19-26. North Holland.
• 193: D. Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences, v.39 n.1, p.51-83, Aug. 1989 [doi>10.1016/0022-0000(89)90019-6]
• 194: LEONE, N., PALOPOLI, L., AND SACCA, D. 1999. On the complexity of search queries. In T. Polle, T. Ripke, and K.-D. Schewe, Eds., Fundamentals of Information Systems, Papers from the Seventh Workshop on Foundations of Models and Languages for Data and Objects, Ostfriesland, Germany, October 5-9, 1998 (FMLDO '98) (1999), pp. 113-127. Kluwer.
• 195: Nicola Leone , Pasquale Rullo , Francesco Scarcello, Disjunctive stable models: unfounded sets, fixpoint semantics, and computation, Information and Computation, v.135 n.2, p.69-112, June 15, 1997 [doi>10.1006/inco.1997.2630]
• 196: LEWIS, H. R. 1979. Unsolvable Classes of Quantificational Formulas. Addison-Wesley, Reading, Mass.
• 197: LEWIS,H.R.AND STATMAN, R. 1982. Unifiability is complete for co-NLogSpace. Information Processing Letters 15, 5 (Dec.), 220-222.
• 198: Leonid Libkin, On the Forms of Locality over Finite Models, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, p.204, June 29-July 02, 1997
• 199: Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182609]
• 200: Leonid Libkin , Limsoon Wong, On representation and querying incomplete information in databases with bags, Information Processing Letters, v.56 n.4, p.209-214, Nov. 24, 1995 [doi>10.1016/0020-0190(95)00154-5]
• 201: Leonid Libkin , Rona Machlin , Limsoon Wong, A query language for multidimensional arrays: design, implementation, and optimization techniques, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.228-239, June 04-06, 1996, Montreal, Quebec, Canada
• 202: Alexei Lisitsa , Vladimir Sazonov, &Dgr;-languages for sets and LOGSPACE computable graph transformers, Theoretical Computer Science, v.175 n.1, p.183-222, March 30, 1997
• 203: LIVCHAK, A. 1983. The relational model for process control. Automatic Documentation and Mathematical Linguistics 4, 27-29. In Russian.
• 204: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 205: Jorge Lobo , Jack Minker , Arcot Rajasekar, Foundations of disjunctive logic programming, MIT Press, Cambridge, MA, 1992
• 206: Zbigniew Lonc , Miroslaw Truszczynski, On the Problem of Computing the Well-Founded Semantics, Proceedings of the First International Conference on Computational Logic, p.673-687, July 01, 2000
• 207: M. J. Maher, Equivalences of logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 208: MAKANIN, G. 1977. The problem of solvability of equations in free semigroups. Matematiceskij Sbornik 103, 2, 147-236. In Russian. English Translation in: Math. USSR Sbornik 32,2, 129-198, 1977.
• 209: Jerzy Marcinkowski, The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.427-438, February 22-24, 1996
• 210: J. Marcinkowski, DATALOG SIRUPs uniform boundedness is undecidable, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.13, July 27-30, 1996
• 211: Jerzy Marcinkowski, Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs, SIAM Journal on Computing, v.29 n.1, p.231-257, Feb. 2000 [doi>10.1137/S0097539797322140]
• 212: MARCINKOWSKI,J.AND PACHOLSKI, L. 1992. Undecidability of the Horn-clause implication problem. In 33rd Annual Symposium on Foundations of Computer Science (FOCS '92) (Pittsburgh, Pennsylvania, 24-27 Oct. 1992), pp. 354-362. IEEE Computer Society Press.
• 213: Wiktor Marek , Mirosław Truszczyński, Autoepistemic logic, Journal of the ACM (JACM), v.38 n.3, p.587-618, July 1991 [doi>10.1145/116825.116836]
• 214: MAREK,V.W.,NERODE, A., AND REMMEL, J. B. 1992. How complicated is the set of stable models of a recursive logic program? Annals of Pure and Applied Logic 56, 1-3 (April), 119-135.
• 215: MAREK,V. .,NERODE, A., AND REMMEL, J. B. 1994. The stable models of a predicate logic program. Journal of Logic Programming 21, 3 (Nov.), 129- 153.
• 216: Victor W. Marek , Anil Nerode , Jeffrey B. Remmel, On the Complexity of Abduction, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.513, July 27-30, 1996
• 217: MAREK,V.W.,RAJASEKAR, A., AND TRUSZCZYNSKI,M. 1995. Complexity of computing with extended propositional logic programs. Annals of Mathematics and Artificial Intelligence 15, 3-4, 357- 378.
• 218: MARKUSZ,Z.AND KAPOSI, A. A. 1982. A design methodology in Prolog programming. In M. van Caneghem, Ed., Proceedings of the First International Logic Programming Conference, September, 14-17th, 1982. Faculte des Science de Luminy, ADDP-GIA, Marseille, France (ICLP '82) (Sept. 1982), pp. 139-145.
• 219: MARTELLI,A.AND MONTANARI, U. 1976. Unification in linear time and space: A structured presentation. Technical Report B76-16 (Nota Interna), IEI, Consiglio Nazionale delle Ricerche, Pisa, Italy.
• 220: Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
• 221: MATIYASEVI C, Y. V. 1970. Enumerable sets are Diophantine. Doklady Akademii Nauk SSSR 191, 2, 279-282. In Russian. English Translation in: Soviet Mathematical Doklady 11, 354-357, 1970.
• 222: David A. McAllester, Automatic recognition of tractability in inference relations, Journal of the ACM (JACM), v.40 n.2, p.284-303, April 1993 [doi>10.1145/151261.151265]
• 223: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• 224: J. Minker, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 225: MINKER, J. 1994. Overview of disjunctive logic programming. Annals of Mathematics and Artificial Intelligence 12, 1,2 (Dec.), 1-24.
• 226: Jack Minker, Logic and Databases: A 20 Year Retrospective, Proceedings of the International Workshop on Logic in Databases, p.3-57, July 01-02, 1996
• 227: MINKER,J.AND NICOLAS, J.-M. 1983. On recursive axioms in deductive databases. Information Systems 8, 1, 1-13.
• 228: Jack Minker , Carolina Ruiz, Semantics for disjunctive logic programs with explicit and default negation, Fundamenta Informaticae, v.20 n.1-3, p.145-192, March/April/May 1994
• 229: MUGGLETON, S. 1992. Inductive logic programming. In S. Muggleton, Ed., Inductive Logic Programming, pp. 3-28. Academic Press.
• 230: Paliath Narendran , Friedrich Otto, Some results on equational unification, Proceedings of the tenth international conference on Automated deduction, p.276-291, July 1990, Kaiserslautern, Germany
• 231: NAUGHTON, J. F. 1989. Data independent recursion in deductive databases. Journal of Computer and System Sciences 38, 2 (April), 259-289.
• 232: J. F. Naughton , Y. Sagiv, A decidable class of bounded recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-236, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28684]
• 233: Jeffrey F. Naughton , Yehoshua Sagiv, A simple characterization of uniform boundedness for a class for recursions, Journal of Logic Programming, v.10 n.3-4, p.233-253, April/May 1991 [doi>10.1016/0743-1066(91)90037-P]
• 234: Vít Ochozka , Olga Stepánková , Petr Stepánek, Normal Forms and the Complexity of Computations of Logic Programs, Proceedings of the 2nd Workshop on Computer Science Logic, p.357-371, October 03-07, 1988
• 235: Martin Otto , Jan Van den Bussche, First-order queries on databases embedded in an infinite structure, Information Processing Letters, v.60 n.1, p.37-41, Oct. 14, 1996 [doi>10.1016/S0020-0190(96)00140-8]
• 236: Luigi Palopoli, Testing logic programs for local stratification, Theoretical Computer Science, v.103 n.2, p.205-234, 14 Sept. 1992 [doi>10.1016/0304-3975(92)90013-6]
• 237: PAPADIMITRIOU, C. H. 1985. Anote on the expressive power of Prolog. Bulletin of the EATCS 26, 21- 23.
• 238: PAPADIMITRIOU, C. H. 1994. Computational Complexity. Addison-Wesley.
• 239: Christos H. Papadimitriou , Mihalis Yannakakis, A note on succinct representations of graphs, Information and Control, v.71 n.3, p.181-185, Dec. 1986 [doi>10.1016/S0019-9958(86)80009-2]
• 240: 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]
• 241: Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
• 242: Jan Paredaens , Jan Vanden Bussche , Dirk Van Gucht, First-Order Queries on Finite Structures Over the Reals, SIAM Journal on Computing, v.27 n.6, p.1747-1763, Dec. 1998 [doi>10.1137/S009753979629766]
• 243: PATERSON,M.S.AND WEGMAN, M. N. 1978. Linear unification. Journal of Computer and System Sciences 16, 2 (April), 158-167.
• 244: David Pearce , Gerd Wagner, Logic programming with strong negation, Proceedings of the international workshop on Extensions of logic programming, p.311-326, February 1991, Tu¨bingen, Germany
• 245: Ch. Pollet , Jeffrey B. Remmel, Non-Monotonic Reasoning with Quantified Boolean Constraints, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, p.18-39, July 28-31, 1997
• 246: 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
• 247: PRZYMUSINSKI, T. C. 1988b. Perfect model semantics. In R. A. Kowalski and K. A. Bowen, Eds., Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (ICLP/SLP '88) (Aug. 1988), pp. 1081-1096. MIT Press.
• 248: dPRZYMUSINSKI, T. C. 1991. Stable semantics for disjunctive programs. New Generation Computing 9, 3/4, 401-424.
• 249: PRZYMUSINSKI, T. C. 1995. Static semantics for normal and disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 14, 2-4 (Sept.), 323-357.
• 250: RENEGAR, J. 1988. A faster PSPACE algorithm for deciding the existential theory of the reals. In 29th Annual Symposium on Foundations of Computer Science (White Plains, New York, 24- 26 Oct. 1988), pp. 291-295. IEEE.
• 251: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 252: ROSATI, R. 1997. Reasoning with minimal belief and negation as failure: Algorithms and complexity. In Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-- 31, 1997, Providence, Rhode Island (July 1997), pp. 430-435. AAAI Press/MIT Press.
• 253: ROSATI, R. 1998. Expressiveness vs. complexity in nonmonotonic knowledge bases: Propositional case. In H. Prade, Ed., 13th European Conference on Artificial Intelligence, Brighton, UK, August 23-28 1998, Proceedings (ECAI '98) (Chichester, Aug. 1998), pp. 47-48.
• 254: Domenico Saccà, Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries, Proceedings of the 5th International Conference on Database Theory, p.353-367, January 11-13, 1995
• 255: Domenico Saccà, The expressive powers of stable models for bound and unbound DATALOG queries, Journal of Computer and System Sciences, v.54 n.3, p.441-464, June 1997 [doi>10.1006/jcss.1997.1446]
• 256: Yehoshua Sagiv, On computing restricted projections of representative instances, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.171-180, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325427]
• 257: Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 258: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 259: SAKAMA,C.AND INOUE, K. 1994a. An alternative approach to the semantics of disjunctive logic programs and deductive databases. Journal of Automated Reasoning 13, 1, 145-172.
• 260: Chiaki Sakama , Katsumi Inoue, On the equivalence between disjunctive and abductive logic programs, Proceedings of the eleventh international conference on Logic programming, p.489-503, August 1994
• 261: SAVITCH, W. J. 1970. Relationship between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4,2 (April), 177-192.
• 262: Vladimir Yu. Sazonov, Hereditarily-finite sets, data bases and polynomial-time computability, Theoretical Computer Science, v.119 n.1, p.187-214, Oct. 11, 1993
• 263: Vladimir Yu. Sazonov , Alexei Lisitsa, Delta-Languages for Sets and sub-PTIME Graphs Transformers, Proceedings of the 5th International Conference on Database Theory, p.125-138, January 11-13, 1995
• 264: John S. Schlipf, The expressive powers of the logic programming semantics (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.196-204, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298564]
• 265: SCHLIPF, J. S. 1995a. Complexity and undecidability results for logic programming. Annals of Mathematics and Artificial Intelligence 15, 3-4, 257-288.
• 266: John S. Schlipf, The expressive powers of the logic programming semantics, Journal of Computer and System Sciences, v.51 n.1, p.64-86, Aug. 1995
• 267: SCHOLZ,H.AND HASENJAEGER, G. 1961. Grundz~ge der mathematischen Logik. Springer, Berlin.
• 268: SEBELYK,J.AND STEPANEK, P. 1982. Horn clause programs for recursive functions. In K. L.Clark and S.-A a .Tarnlund, Eds., Logic Programming, pp. 325-340. Academic Press.
• 269: J. Seitzer , John S. Schlipf, Affordable Classes of Normal Logic Programs, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, p.92-111, July 28-31, 1997
• 270: Ehud Y. Shapiro, Alternation and the computational complexity of logic programs, Journal of Logic Programming, v.1 n.1, p.19-33, June 1984 [doi>10.1016/0743-1066(84)90021-9]
• 271: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• 272: SMULLYAN, R. 1961. Theory of Formal Systems. Princeton University Press, Princeton, New Jersey. Annals of Mathematical Studies Vol 47.
• 273: SMULLYAN, R. M. 1956. On definability by recursion (Abstract 782t). Bulletin AMS 62, 601.
• 274: Petr Śtěpánek , Olga Śtěpáneková, Logic programs and alternation, Proceedings on Third international conference on logic programming, p.99-106, September 1986, London, United Kingdom
• 275: STEP~NKOV~,O.AND STEP~ ANEK, P. 1984. Transformations of logic programs. Journal of Logic Programming 1, 4 (Dec.), 305-318.
• 276: Dan Suciu, Bounded fixpoints for complex objects, Theoretical Computer Science, v.176 n.1-2, p.283-328, April 20, 1997 [doi>10.1016/S0304-3975(96)00293-9]
• 277: T~RNLUND, S.-A a . 1977. Horn clause computability. BIT 17,2, 215-226.
• 278: TURING, A. M. 1936-1937. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society Series 2, 42, 230-265. Corrections ibid. 544-546. Reprinted in {Davis 1965}.
• 279: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 280: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 281: ULLMAN,J.D.AND VAN GELDER, A. 1988. Parallel complexity of logical query programs. Algorithmica 3, 5-42.
• 282: Kumar Vadaparty, On the power of rule-based languages with sets, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113416]
• 283: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
• 284: Ron van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Journal of Computer and System Sciences, v.54 n.1, p.113-135, Feb. 1997 [doi>10.1006/jcss.1997.1455]
• 285: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 286: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• 287: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 288: Jan van Leeuwen, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 289: VANDEURZEN, L., GYSSENS, M., AND VAN GUCHT, D. 1996. On query languages for linear queries definable with polynomial constraints. In Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, Cambridge, Massachusetts, USA, August 19-22, 1996, Number 1118 in Lecture Notes in Computer Science (Aug. 1996), pp. 468--481.
• 290: 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]
• 291: Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]
• 292: 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]
• 293: VEITH, H. 1994. Logical reducibilities in finite model theory. Master's thesis, Information Systems Department, TU Vienna, Austria.
• 294: Helmut Veith, Succinct representation, leaf languages, and projection reductions, Information and Computation, v.142 n.2, p.207-236, May 2, 1998 [doi>10.1006/inco.1997.2696]
• 295: Victor Vianu, Rule-based languages, Annals of Mathematics and Artificial Intelligence, v.19 n.1-2, p.215-259, 1997 [doi>10.1023/A:1018907806177]
• 296: Sergei Vorobyov , Andrie Voronkov, Complexity of nonrecursive logic programs with complex values, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-253, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275515]
• 297: VORONKOV, A. 1995. On computability by logic programs. Annals of Mathematics and Artificial Intelligence 15, 3-4, 437-456.
• 298: Limsoon Wong, Normal forms and conservative extension properties for query languages over collection types, Journal of Computer and System Sciences, v.52 n.3, p.495-505, June 1996 [doi>10.1006/jcss.1996.0037]
• 299: YANNAKAKIS, M. 1981. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings (VLDB '81) (Sept. 1981), pp. 82-94. IEEE Computer Society Press.
• 300: YASUURA, H. 1984. On parallel computational complexity of unification. In Fifth Generation Computer Systems 1984, Proceedings of the International Conference on Fifth Generation Computer Systems 1984, Tokyo, Japan, November 6- 9, 1984 (FGCS '84) (1984), pp. 235-243. Institute for New Generation Computer Technology (ICOT): OHMSHA and North-Holland.
• 301: YOU, J.-H. AND YUAN, L.-Y. 1995. On the equivalence of semantics for normal logic programming. Journal of Logic Programming 22,3 (March), 211-222.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Theory

Keywords:
Complexity, datalog, expressive power, logic programming, nonmonotonic logic, query languages