Research in
Computer Science

The Theory and Logical Foundations of Computing Group of CIn-UFPE, though small, is rather active in the two subareas of Theoretical Computer Science:
(i) Algorithms and Computational Complexity (Theory-A), in particular, String Matching Algorithms (and applications in Computational Biology), Approximating Algorithms for Graph Problems;
(ii) Formal Models and Semantics (Theory-B), particularly, Proof Theory, Proof Complexity and its relationship to Computational Complexity, Model Theory and its relationship to Descriptive Complexity and the Expressive Power of Query Languages, Foundations of Cryptography, Semantics and Models of Concurrent Processes.
(iii) The group has sought to act also in the gap subareas between "Theory-A" and "Theory-B", in particular, Logical Foundations of of Complexity Theory, Descriptive Complexity and Finite Model Theory, Algebraic Complexity, Proof Complexity.