Subject description - AE4M33AU

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
AE4M33AU Automatic Reasoning Extent of teaching:2+2c
Guarantors:  Roles:PO,V Language of
teaching:
EN
Teachers:  Completion:Z,ZK
Responsible Department:13136 Credits:6 Semester:L

Anotation:

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.

Course outlines:

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.

Exercises outline:

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.

Literature:

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

Requirements:

Rozpoznávání a strojové učení, Pokročilé metody reprezentace znalosti

Subject is included into these academic programs:

Program Branch Role Recommended semester
MEKME1 Wireless Communication V 4
MEKME5 Systems of Communication V 4
MEKME4 Networks of Electronic Communication V 4
MEKME3 Electronics V 4
MEKME2 Multimedia Technology V 4
MEOI1 Artificial Intelligence PO 4
MEEEM1 Technological Systems V 4
MEEEM5 Economy and Management of Electrical Engineering V 4
MEEEM4 Economy and Management of Power Engineering V 4
MEEEM3 Electrical Power Engineering V 4
MEEEM2 Electrical Machines, Apparatus and Drives V 4
MEKYR4 Aerospace Systems V 4
MEKYR1 Robotics V 4
MEKYR3 Systems and Control V 4
MEKYR2 Sensors and Instrumentation V 4


Page updated 16.7.2019 09:52:42, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)