|
E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374-425, September 2001.
This paper 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.
Highly theoretical. The text is, however, largely self-contained and most concepts (e.g., complexity classes) are clearly defined.
Like most survey papers this paper is long (~70 pages).
The connections between complexity classes and different logics is well known. It is nice to see the connection made even stronger by studying logic programming.
Posted to Logic/Declerative by Ehud Lamm on 2/7/02; 8:50:47 AM
|
|
Complexity and expressive power of logic programming
