# Generalized model-checking over locally tree-decomposable classes

Markus Frick Albert-Ludwigs-Universität Freiburg 4pm Tuesday 9 October 2001 Room 2511, JCMB, King's Buildings

In 1999, Frick and Grohe proved that properties of graphs or other
relational structures that are definable in first-order logic can be
*decided* in linear time when the input structures are
restricted to come from a *locally tree-decomposable* class of
structures. Examples of such classes are the class of planar graphs
or classes of graphs of bounded valence.

In this talk, we consider more general computational problems than
decision problems. We prove that *construction*,
*listing*, and *counting* problems definable in
first-order logic can be solved in linear time on locally
tree-decomposable classes of structures.