Various forms of logic programming have been invented and used in the last 20 years, for example, logic programming with (several forms of) negation, disjunctive logic programming, inductive logic programming, and so on. Complexity theory is a well-suited instrument for comparing the strength of different forms of logic programming, and for describing the expressive power of these formalisms. In this talk we will give a survey of complexity results on logic programming. We will carefully explain that complexity is not only a quantitative, but also a deeply qualitative measure of the strength of a logical language. We will also discuss some interesting complexity problems in the context of inductive logic programming.
Georg Gottlob is a Professor of Computer Science at the Vienna University of Technology (TU Wien), where he currently chairs the department of Information Systems and the industry-funded Christian Doppler Expert Systems Lab. His research interests are nonmonotonic reasoning, logic programming, database theory (in particular, query languages), finite model theory, and computational complexity. On the more applied side, he supervises a number of industry projects dealing with expert systems and with multimedia information systems. Dr. Gottlob holds his current position since 1988. Before that, he was affiliated with the Italian National Research Council in Genoa, Italy, and before with the Politecnico di Milano, Italy. He has taught several times at Stanford University. He was or is an invited speaker at several international conferences or workshops, is on the editorial board of a number of journals and chaired (or chairs) the Program Committee of conferences such as ICDT'95 and CSL'98. Gottlob had a fundamental role in the determination of the complexity and expressive power of various forms of nonmonotonic reasoning, which became a major issue in the last years. Publications authored or co-authored by Gottlob have appeared in Journals such as JACM, SIAM J. Computing, JCSS, Information and Computation, and Journal of Symbolic Logic. Check out Georg Gottlob's home page at the Vienna University of Technology.