Model-checking problems, machines and parameterized complexity [Elektronische Ressource] / vorgelegt von Yijia Chen

Model-Checking Problems, Machinesand Parameterized ComplexityDissertationzur Erlangung des Doktorgradesder Fakult¨at fu¨r Mathematik und Physikder Albert-Ludwigs-Universit¨at Freiburg im Breisgauvorgelegt vonYijia ChenJuni 2004Dekan: Prof. Dr. Dr. h.c. Rolf SchneiderErster Referent: Prof. Dr. Jo¨rg FlumZweiter Referent: Prof. Dr. Bernhard NebelDatum der Promotion: 20. September 2004iiContents1 Introduction 12 Preliminaries 72.1 First-order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.1 Classical Complexity . . . . . . . . . . . . . . . . . . . . . 92.2.2 Parameterized Complexity . . . . . . . . . . . . . . . . . . 113 Model-Checking on Arbitrary Structures 173.1 Structures with Functions . . . . . . . . . . . . . . . . . . . . . . 203.2 A Remark on Relational Structures . . . . . . . . . . . . . . . . . 304 Machine Characterizations 334.1 The Class W[P] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.1.1 Monotone and Anti-monotone Circuits . . . . . . . . . . . 354.1.2 Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2 The Class W[1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.3 The Classes of the A-Hierarchy . . . . . . . . . . . . . . . . . . . 494.3.1 The Classes AWP[t] and AW[P] . . . . . . . . . . . . . . . 52func4.4 The Classes of the W -Hierarchy . . . . . . . . . . . . . . . . . 544.4.