Theory of Computation

The Theory of Computing area aims to provide rigorous mathematical foundations for the various areas of Informatics. The group of researchers that make up the Department is involved in projects ranging from formal logic to denotational semantics, program construction calculations and the design and analysis of sequential and parallel algorithms. In the area of ​​formal logic, significant results have been obtained on generalizations of the concepts of extension, interpretation and implementation between theories for any logics. In the area of ​​algebraic logic, an extended relational algebra, known as Fork-Algebra, was developed – the first finitely axiomatizable algebra of first-order logic with equality. In the area of ​​language semantics, different lambda-calculi have been developed based on substructural logics with topological-categorical models, with the main objective of a structural characterization of concurrency/parallelism. In the area of ​​formal program construction, both a non-deterministic programming calculation and several formal models of the software development process and tools to support them were developed. In the area of ​​algorithm design and analysis, special attention is given to the development of sequential and parallel algorithms for problems of combinatorial optimization, graph theory and linear/integer/dynamic programming, often involving applications in practical problems in computing, automation and engineering.