- FINITE MODEL THEORY AND LINKS TO COMPUTER
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
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.