Technical Reports

The report FIMU-RS-2010-12

Disjunctive Modal Transition Systems and Generalized LTL Model Checking

by Nikola Bene¹, Ivana Èerná, Jan Køetínský, November 2010, 44 pages.

FIMU-RS-2010-12. Available as Postscript, PDF.

Abstract:

Modal transition systems (MTS) is a well established formalism used for specification and for abstract interpretation. We consider its disjunctive extension (DMTS) and we show that refinement problems for DMTS are not harder than in the case of MTS. There are two main results in the paper. Firstly, we give a solution to the common implementation and specification problems lowering the complexity from EXPTIME to PTIME. Secondly, we identify a fundamental error made in previous attempts at LTL model checking of MTS and provide algorithms for LTL model checking of MTS and DMTS. Moreover, we show how to apply this result to compositional verification and circumvent the general incompleteness of the MTS composition.