Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2559
Authors: Göller, Stefan
Lohrey, Markus
Title: Fixpoint logics on hierarchical structures
Issue Date: 2005
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2005,4
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-24305
http://elib.uni-stuttgart.de/handle/11682/2576
http://dx.doi.org/10.18419/opus-2559
Abstract: 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. In this paper, the model-checking problem for the modal $\mu$-calculus and (monadic) least fixpoint logic on hierarchically defined input graphs is investigated. In order to analyze the modal $\mu$-calculus, parity games on hierarchically defined input graphs are investigated. In most cases precise upper and lower complexity bounds are derived. A restriction on hierarchical graph definitions that leads to more efficient model-checking algorithms is presented.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2005_04.pdf314,05 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.