THEORETICAL 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.

* Last updated November 26, 2003, 11:40:06 GMT-0200
**
*

*
*