Home
Researchers
Meetings and other events
Positions
Publications
Research
Reports
Newsletter
Useful links

I
II
III
IV
V
VI
VII
VIII

MODNET
Research Training Network in Model Theory



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