Complexity and expressive power of logic programming
- 1 September 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 33 (3), 374-425
- https://doi.org/10.1145/502807.502810
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.Keywords
This publication has 191 references indexed in Scilit:
- On the Equivalence of Recursive and Nonrecursive Datalog ProgramsJournal of Computer and System Sciences, 1997
- Extending Datalog with arraysData & Knowledge Engineering, 1995
- The power of languages for the manipulation of complex valuesThe VLDB Journal, 1995
- Computing with First-Order LogicJournal of Computer and System Sciences, 1995
- Datalog vs first-order logicJournal of Computer and System Sciences, 1994
- Domain independence and the relational calculusActa Informatica, 1994
- Negation by default and unstratifiable logic programsTheoretical Computer Science, 1991
- Negation in rule-based database languages: a surveyTheoretical Computer Science, 1991
- Data independent recursion in deductive databasesJournal of Computer and System Sciences, 1989
- On recursive axioms in deductive databasesInformation Systems, 1983