Fourth Annual IEEE Symposium on

Logic in Computer Science (LICS 1989)

Paper: Compositional model checking (at LICS 1989)

Authors: Clarke, E.M. Long, D.E. McMillan, K.L.


A method is described for reducing the complexity of temporal logic model checking in systems composed of many parallel processes. The goal is to check properties of the components of a system and then deduce global properties from these local properties. The main difficulty with this type of approach is that local properties are often not preserved at the global level. The authors present a general framework for using additional interface processes to model the environment for a component. These interface processes are typically much simpler than the full environment of the component. By composing a component with its interface processes and then checking properties of this composition, the authors can guarantee that these properties will be preserved at the global level. They give two example compositional systems based on the logic CTL


    author = 	 {Clarke, E.M. and Long, D.E. and McMillan, K.L.},
    title = 	 {Compositional model checking},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {353--362},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}