LOGIC FOR APPLICATIONS

Academic Year 2022-2023

Teachers

Giovanna D'agostino

Unit Credits

Teaching Period

First Period

Course Type

Supplementary

Prerequisites. An introductory course to logic, with syntax and semantics of first order logic.

Teaching Methods. Frontal lessons plus homework exercises

Verification of Learning. The exam is divided into a written and an oral exam.

The written exam consists in the resolution of exercises.

Oral exam on the program, or on further materials.

More Information. If there are

students fora abroad, the course can be given in english.

Objectives

Objective of the course is to highlight how the Computer Science applications mentioned above account for the developments of techniques and results which are specific to final model theory, and do not have a correspondence in the classical model theory. For example, we will show how logics over finite models are the staring point for developing database query languages, and finite model theory techniques are used for proving results about their expressiveness and complexity.

“Systems” which are the object of study of Computer Science are mostly finite objects. Formal languages are used in informatics to

formalise properties of systems, but the most used logic, classical logic, deals with all structures, finite and infinite. Thanks to the applications to Computer Science a new theory arises, the so called Finite Model Theory, which is very different from classical model theory and has application in

Foundation of Data Bases, Complexity Theory, Formal Languages and other parts of Computer Science.

This course aims to provide an introduction to Finite Model Theory with applications to the Foundation of Data Bases and Complexity Theory.

We will deal with the intertwine between Logic, Game theory, Computational Complexity and Data Bases queries.

Texts

-L. Libkin, Finite Model Theory;

– Foundation of Data Bases,

Abiteboul, Hull, Vianu, Addison Wesley.

Articles and the materials from the teacher.

Academic Year 2022-2023