Sequent calculi for process verification: Hennessy-Milner logic for an arbitrary GSOS
We argue that, by supporting a mixture of "compositional" and "structural" styles of proof, sequent-based proof systems provide a useful framework for the formal verification of processes. As a worked example, we present a sequent calculus for establishing that processes satisfy assertions in Hennessy-Milner logic. The main novelty lies in the use of the operational semantics to derive introduction rules, on the left and right of sequents, for the operators of the process calculus. This gives a generic proof system applicable to any process algebra with an operational semantics specified in the GSOS format. Using a general algebraic notion of GSOS model, we prove a completeness theorem for the cut-free fragment of the proof system, thereby establishing the admissibility of the cut rule. Under mild (and necessary) conditions on the process algebra, an omega-completeness result, relative to the "intended" model of closed process terms, follows. (C) 2004 Elsevier Inc. All rights reserved.
formal verification sequent calculus process algebra compositionality structural operational semantics