Embedded systems are increasingly being deployed in a wide variety of applications. Most, if not all, of these applications involve an electronic controller with discrete behaviour controlling a continuously evolving plant. Because of their hybrid behaviour (discrete and continuous) and reactive behaviour, the formal veri cation of embedded systems pose new challenges. Linear Hybrid Automata (LHA) is a language for specifying systems with linear hybrid behaviour. Abstract interpretation is a formal theory for approximating the semantics of programming languages. Model checking is a technique to verify the reactive behaviour of concurrent systems. Computation Tree Logic (CTL) is a temporal property speci cation language. Logic programming is a general purpose programming language based on predicate logic.
In this dissertation, the LHA models are veri ed by encoding them as constraint logic programs. The constraint logic program (CLP) encoding an LHA model is rst specialised and then a concrete minimal model (or possibly an abstract minimal model) for the residual program is computed. The abstract minimal model is computed by applying the theory of abstract interpretation. The computed minimal model forms the basis for verifying the LHA model. We consider two techniques to verify the reactive properties speci ed as CTL formulas: (i) reachability analysis and (ii) model checking.
A systematic translation of LHA models into constraint logic programs is de ned. This is mechanised by a compiler. To facilitate forward and backward reasoning, two di erent ways to model an LHA are de ned. A framework consisting of general purpose constraint logic program tools is presented to accomplish the reachability analysis to verify a class of safety and liveness properties. A tool to compute the concrete minimal model is implemented. The model checking of CTL is de ned as a concrete CTL-semantic function.
Since model checking of in nite state systems, which LHAs are, does not terminate, we apply the theory of abstract interpretation to model checking that ensures termination at the cost of loss in precision. An abstract CTL-semantic function is constructed as an abstract interpretation of the CTL-semantic function. This abstract CTL-semantic function is implemented using a SMT solver resulting in an abstract model checker. We consider two abstract domains: (i) the domain of constraints and (ii) the domain of convex polyhedra, for both abstract model checking and abstract minimal model computation.
We demonstrate the applicability of the proposed theory with examples taken from the literature.