Technischer Bericht TR-2006-04

Bibliograph.
Daten
Göller, Stefan; Lohrey, Markus: Infinite State Model-Checking of Propositional Dynamic Logics.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2006/04.
47 Seiten, englisch.
CR-Klassif.F.1.3 (Complexity Measures and Classes)
F.4.1 (Mathematical Logic)
Keywordsinfinite state systems; model checking; propositional dynamic logic; basic parallel processes; basic process algebras; pushdown systems; prefix-recognizable sytems
Kurzfassung

Model-checking problems for propositional dynamic logic (PDL) and its extension PDL$^\cap$ (which includes the intersection operator on programs) over various classes of infinite state systems (BPP, BPA, pushdown systems, prefix-recognizable systems) are studied. Precise upper and lower bounds are shown for the data/expression/combined complexity of these model-checking problems.

Volltext und
andere Links
PDF (420573 Bytes)
PostScript (688567 Bytes)
Kontaktgoeller@informatik.uni-stuttgart.de lohrey@informatik.uni-stuttgart.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum8. Februar 2006
   Publ. Informatik