MODNET
Research Training Network in Model Theory
Research > Task VIII: Finite model theory and links to computer science

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.


Progress

Years 1 and 2, Years 3 and 4.

Last updated: September 9 2009 15:55 Please send your corrections to: