Personal tools
You are here: Home Events Abstract Archives 2001 Generalized model-checking over locally tree-decomposable classes

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.

Document Actions