Required in stage
First term
Second term
Both terms
This year
Next year
Alternating years
External
Prerequisites
Taught by
Language of instruction
Duration
LevelComputational Logic (B-KUL-H02A9A)
Aims
Computational Logic is founded in Kowalski's famous equation: Algorithm = Logic + Control. According to this view, algorithms consist of a problem description (the logic part) along with a strategy to carry out useful computations on this description (the control part). Computational logic is embodied in the field of logic programming. The language Prolog is an early representative. It is a powerful and flexible programming language with a well established declarative semantics rooted in mathematical logic. Several non trivial common sense reasoning problems in Artificial Intelligence have an elegant solution in Prolog. On the one hand, the resulting solutions are actual programs, fit for computer execution. On the other hand, the above mentioned declarative semantics provides them with a concise and appealing formal meaning, independent of operational aspects.
The aim is to offer an introduction to the field of Logic Programming. The accent lies on understanding and learning to manipulate the concepts involved, not on proving theorems. After completing the course, students should:
- have a good understanding of the main semantics of logic programs and how they relate to each other.
- have a good understanding of principles of program analysis and their application on logic programs
Previous knowledge
- Students should be able to write small programs in the logic programming language Prolog or in another logic programming language and should understand their execution (have taken e.g. one of the courses Programming Languages and Programming Methodologies, Declaratieve talen or Studie van declaratieve talen
- While the course tries to minimize the amount of formal mathematics, some interest in logic and in formal reasoning is necessary.
Course material
Articles and literature
Examples and samples
Is also included in other courses
-
Master of Artificial Intelligence
60 ects.
- Master in de informatica (uitdovend, enkel 2e fase) (Specialisation: Artificial Intelligence) 120 ects.
- Master in de ingenieurswetenschappen: computerwetenschappen (Specialisation: Artificial Intelligence) 120 ects.
Activities
3.0 ects. Computational Logic: Lecture (B-KUL-H02A9a)
Content
The course consists of two parts:
Part I covers semantics of logic programs:
- A quick rehearsal of the semantics of definite programs which stresses the elegant mathematical build-up of the underlying theory.
- A broad overview of the main semantics for logic programs with negation that shows the evolution in the insight about the right semantics and includes completion semantics, well founded semantics, inductive definitions and stable model semantics. This is partially based on the research in the group on the use of inductive definitions for knowledge representation and problem solving.
Part II covers various aspects of program analysis
and applies them on logic programs:
- Termination of logic programs
- Abstract interpretation with application on logic programs
- Program specialisation with application on logic programs.Each of these topics is related to past or ongoing research in the group.
Description of learning activities
Exercises are interweaven with lectures.
Course material
Slides are available.
Further background material for Part I can be found in:
- J.W. Lloyd, Foundations of Logic Programming, Springer Verlag.
- K.R. Apt, Logic Programming, Ch. 10 in Handbook of TheoreticalComputer Science, Ed. J.~Van Leeuwen, Elsevier.
- K.R. Apt and R.N. Bol, Logic Programming and Negation: A Survey, Journal of Logic Programming, Vol. 19/20: 9-71, 1994. Special Issue: Ten Years of Logic Programming, Eds. M. Bruynooghe, S. Debray, M. Hermenegildo and M. Maher.
- A. Van Gelder, K.A. Ross and J.S. Schlipf, The well-founded semantics for general logic programs, J. ACM, Vol 38(3): 620--650, July 1991.
- M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, Proc. Fifth Int. Conf. and Symp. on Logic Programming, eds. R.A. Kowalsi and K.A. Bowen, pp. 1070--1080, MIT press 1988.
- M. Denecker, M. Bruynooghe and V. Marek, Logic programming revisited: logic programs as inductive definitions, ACM Transactions on Computational Logic Vol 2(4): 623--654, October 2001.
For Part II, further material can be found in:
- D. De Schreye, S. Decorte, Termination of Logic Programs: the Never Ending Story, J. Logic Programming, Vol 19-20:199--260, 1994.
- K.R. Apt and D. Pedreschi. Reasoning about Termination of Pure Prolog Programs. Information and Computation, Vol 106: 109--157, 1993.
- K.R. Apt, M. Bezem Acyclic Programs. New Generation Computing Vol 9: 335--363 (1991).
- M. Bezem. Strong termination of logic programs. Journal of Logic Programming, Vol 15:79--97, 1993.
- Patrick Cousot, Radhia Cousot: Abstract Interpretation and Application to Logic Programs. J. Log. Program. 13(2&3): 103-179 (1992)
- M. Bruynooghe, and D. Boulanger, Abstract interpretation for (constraint) logic programming, In Constraint Programming, (Mayoh, B. and Tyugu, E. and Penjam, J., eds.), vol. F/131, NATO ASI Series, Springer-Verlag, 1994, pp.228-258
- M. Leuschel and M. Bruynooghe, Logic program specialisation through partial deduction: Control issues, Theory and Practice of Logic Programming Vol 2(4\&5), 2002, pp 461--515.
1.0 ects. Computational Logic: Exercises (B-KUL-H02K9a)
Content
Small exercises that force the students to apply the concepts introduced in the lectures.
Aims
Help the students in mastering the concepts introduced in the lectures.
Description of learning activities
Students solve small exercises and can ask for clarifications.
Course material
Set of exercises and solutions.
Evaluation
Evaluation : Computational Logic (B-KUL-H22A9a)
Explanation
Oral exam with written preparation.
The exam consists of solving a number of exercises (closed book). The answers should show mastery of the underlying concepts.
