Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-2295
URL: http://www.freidok.uni-freiburg.de/volltexte/229/

Frick, Markus

Easy instances for model checking

Einfache Fälle für Model Checking

Dokument1.pdf (650 KB) (md5sum: e615208a5ff823127d67ff4290a10f0f)

Kurzfassung in Deutsch

Our interest is focused on the complexity of the model-checking problem and its generalizations. This question is intimately related to the expressibility of the logical language in question. We investigate the parameterized complexity of queries expressible in monadic second order logic over tree-like structures (structures with bounded tree-width) and first order logic over locally tree-like structures. The importance of the latter stems from the fact that structures of bounded valence, planar graphs and graphs with bounded crossing number are all locally tree-like. And thus our results apply to these classes.

For each of these two questions we consider the following questions: (i) decide, if a query hold in a structure (ii) compute an assignment that make a query true in a structure (iii) compute all satisfying assignments and (iv) compute the number of satisfying assignments.

We give algorithms that solve these questions in optimal time, i.e. in time linear in the size of the structure (+ the output, if there is noteworthy output). In particular, we show that counting the number of dominating set of size k can be done in linear time on planar graphs.

SWD-Schlagwörter: Model checking , Berechnungskomplexität , Kombinatorik
Freie Schlagwörter (englisch): parameterized complexity , treewidth , algorithms , logic
CCS Klassifikation G.2.1 G.2.
Institut: Institut f. Math. Logik u. Grundlagen d. Mathematik
Fakultät: Mathematische Fakultät (bis Sept. 2002)
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Erstgutachter: Grohe, Martin (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 20.06.2001
Erstellungsjahr: 2001
Publikationsdatum: 17.08.2001