Department of Theoretical Computer Science

The research in our department follows two directions. The first one concerns non-classical logics. We focus mainly on substructural, fuzzy and modal logics. In the second one we investigate computational complexity by means of specialised computational models like neural networks, branching programs and Boolean functions.

Our Research Area

Logic is an essential tool for the formalization of mathematics and it is suitable also for formal description of many specialized structures, including those that arise from particular applications. Specialized types of logics  are therefore used, e.g., for program or hardware verification.

Computational complexity looks into the problem of determining the least amount of computational resources that is necessary for algorithmic problem solving. Time and computer memory are typical resources of a  computation, however, models with other complexity measures, such as the size and depth of a circuit, the number of memory accesses, energy, parallelism, probabilistic and analog computation, etc., are also  investigated.

We focus on theoretical research in the following areas:

  • Algorithmic properties of substructural logics
  • Algebraic logic
  • Mathematical fuzzy logic
  • Predicate and modal extensions of substructural logic
  • Branching programs for proving lower bounds on space complexity of Turing machines
  • Models of neural networks with nonstandard complexity measures, where, apart from complexity issues, we also analyze learning effectiveness
  • Complexity of Boolean functions, algebraic and combinatorial properties of Boolean functions

Seminar

Our department organizes jointly with the Czech Society for Cybernetics and Informatics a seminar on applied mathematical logic (also called Hájek’s seminar according to its founder) which regularly takes place since the late 1960’s.

Running projects

Publications

Spanning some 900 pages, the two volumes of the Handbook provide an organised, detailed and up-to-date presentation of mathematical fuzzy logic as a significant subfield of mathematical logic. It primarily targets
researchers working in logic and related fields, but will also be useful for readers interested in logical foundations of fuzzy set theory or philosophical and linguistic issues related to vagueness. Five chapters of the  Handbook were (co-)authored by department members.

Activities

Department members