Automatic Reasoning

Relations:

It is not possible to register for the course A4M33AU if the student is concurrently registered for or has already completed the course AE4M33AU (mutually exclusive courses).

The requirement for course A4M33AU can be fulfilled by substitution with the course AE4M33AU.

It is not possible to register for the course A4M33AU if the student is concurrently registered for or has previously completed the course AE4M33AU (mutually exclusive courses).

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Computer Science

Synopsis:

Theorem proving is no more restricted to mathematics, but it is ever more often used in situations, when one needs to make sure that the suggested procedure meets the initial requirements it is used in deductive databases as well as for verification of SW or HW components. The process of proof construction has to be automated for that purpose. The course reviews current systems of 1st order theorem proving and their practical applications. There are explained underlying theoretical principles (model checking, resolution, tableaux) together with their practical and theoretical constraints. Special attention is devoted to gaining experience in choosing the best tool to solve a specific problem, in identification of mistakes in input or in strengthening the obtained results.

Requirements:

Syllabus of lectures:

1. History of automated reasoning in the context of artificial intelligence, review of its historical and up-to-date applications.

2. Problems in Boolean domains: from their specification and representation, to the formal solution. Properties of logical theorem proving - correctness and completness.

3. DPLL method, its existing implementations and their practical applications.

4. Model checking as a tool for verification, applications for finite automata.

5. Model checking - existing systems and how they are used in practice.

6. Automated theorem proving in general domains, language of 1st order logic.

7. Resolution and theorem provers based on this paradigma.

8. Workflow in resolution theorem provers and its basic steps: transformation to clausal form, ANL loop.

9. Non-resolution theorem provers: „tableaux“, equality, transformation to DPLL.

10. Methods and systems for model construction in general domains.

11. Practical and theoretical boundaries for existing methods and systems.

12. Review of current automated theorem provers, their efficiency and practical utilization.

13. Algorithmic complexity of automated theorem provers and choice of the language for knowledge representation.

14. Spare slot.

Syllabus of tutorials:

1.Examples of typical problems for automated reasoning from various domains..

2.Specification of some simple problems in the formal language.

3.Transformation of the specification into the form requested by the theorem prover.

4.The tools for automated theorem proving - hands-on exercise.

5.Specification of more complex problems in the formal language and their automated solution I.

6.Specification of more complex problems in the formal language and their automated solution II.

7.Choice of the tool to be used in a specific problem.

8.Assignment of an individual project its goal is to implement a simple theorem prover applying specific clearly defined strategy or constraint on the used language in order to check impact of this.

9.Transformations of input and output for various theorem provers, interpretation of conclusions.

10.How to find an error in the problem statement.

11.Autonomous work on the assigned project the second part.

12.Simplification and strengthening of the obtained results.

13.Autonomous work on the assigned project the third part.

14.Credits, spare slot.

Study Objective:

Study materials:

Bundy, A.: The Computational Modelling of Mathematical Reasoning, Academic Press 1983 (Bundy). http://www.inf.ed.ac.uk/teaching/courses/ar/book/book-postcript/

Clarke, E.M. Jr., Grumberg, O. and Peled, D. A.: Model Checking, The MIT Press, 1999, Fourth Printing 2002. http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=3730

McCune, W.: Otter 3.3 Reference Manual (http://www-nix.mcs.anl.gov/AR/otter/otter33.pdf)

Newborn, M.: Automated Theorem Proving: Theory and Practice

Robinson, J.A., Voronkov, A. (Eds.): Handbook of Automated Reasoning (in 2 volumes). Elsevier and MIT Press 2001

Weidenbach, Ch.: SPASS: Combining Superposition, Sorts and Splitting (1999)

Wos, L. and Pieper, G.W.: A Fascinating Country in the World of Computing: Your Guide to Automated Reasoning

Note:

Further information:

http://cw.felk.cvut.cz/doku.php/courses/a4m33au/start

No time-table has been prepared for this course

The course is a part of the following study plans: