Analysis of Component Systems

Mila Majster-Cederbaum

(University of Mannheim)

In this talk we discuss approaches to analyse component based systems. We do so in the framework of interaction systems, a generic model for component systems proposed by Joseph Sifakis and Gregor Goessler which strictly separates local behaviour from communication/cooperation. We have shown that deciding properties of component based systems such as deadlock-freedom or liveness of components is PSPACE-hard. We devised several strategies to overcome this complexity problem which we will present in the talk. One approach is to develop sufficient conditions for important properties, that can be tested in polynomial time. Other approaches are e.g. to restrict the architecture of the system or to work with an overapproximation of the global state space that is obtained by exploiting the interaction scheme of the system. Generally
speaking the approaches attempt to derive global properties from the inspection of subsystems.
Tuesday 9th March 2010, 14:00
Robert Recorde Room
Department of Computer Science