Technischer Bericht TR-2005-01

Bibliograph.
Daten
Lohrey, Markus: Model-Checking Hierarchical Structures.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2005/01.
41 Seiten, englisch.
CR-Klassif.F.1.3 (Complexity Measures and Classes)
F.4.1 (Mathematical Logic)
Keywordsmodel-checking; hierarchical structures; logic; complexity
Kurzfassung

Hierarchical graph definitions allow a modular description of graphs using modules for the specification of repeated substructures. Beside this modularity, hierarchical graph definitions also allow to specify graphs of exponential size using polynomial size descriptions. In many cases, this succinctness increases the computational complexity of decision problems when input graphs are defined hierarchical. In this paper, the model-checking problem for first-order logic (FO), monadic second-order logic (MSO), and second-order logic (SO) on hierarchically defined input graphs is investigated. It is shown that in general these model-checking problems are exponentially harder than their non-hierarchical counterparts, where the input graphs are given explicitly. As a consequence, several new complete problems for the levels of the polynomial time hierarchy and the exponential time hierarchy are obtained. Based on classical results of Gaifman and Courcelle, two restrictions on the structure of hierarchical graph definitions that lead to more efficient model-checking algorithms are presented.

Volltext und
andere Links
PDF (353656 Bytes)
PostScript (773726 Bytes)
KontaktSenden Sie eine E-Mail an lohrey@fmi.uni-stuttgart.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum5. Januar 2005
   Publ. Informatik