**TASK VIII
- FINITE MODEL THEORY AND LINKS TO COMPUTER
SCIENCE**

**
Description**

**
List of specific problems**

**VIII.1: Preservation theorems on restricted classes of structures **

a) Modal and guarded fragments,
with links to graph and hypergraph theory.

b) Ehrenfeucht-Fraïssé techniques and bisimulation
in classical versus modal and guarded logics.

c) Preservation under homomorphisms.

**VIII.2: Positive primitive definability and homomorphisms of finite structures **

a) Positive primitive definability and homomorphisms of finite structures

b) Explore links with universal algebra
in applications to constraint satisfaction problems.

c) Develop better algorithms for evaluating pp-formulas

**VIII.3: Descriptive complexity and proof complexity. **

a) Develop a descriptive complexity
of subexponential time solvability and explore connections with parameterized
complexity theory.

b) Apply methods from finite
model theory, in particular Ehrenfeucht-Fraïssé games, in the
context of proof complexity.

c) Extend or simplify Friedgut's conditions
on sharp thresholds in random structures through descriptive complexity.