Compositional Reasoning for Hierarchical State Machines

Abstract

Harel statecharts and its derivatives are popular graphical languages for specifying discrete control systems via hierarchical state machines. Separately, there has been a long line of work on specifying concurrent systems with process calculi which come equipped with an algebraic theory, the ability reason compositionally about various temporal properties, and strong type systems. While these two approaches to modeling systems are tantalizingly similar, the integrated reasoning principles that exist for process calculi have not been demonstrated in hierarchical state machines. A key issue is that operational theories for process calculi do not behave like control systems, and thus, there is virtually no tool support for modeling control systems with such languages. For a control system designer, bringing the integrated, more scalable reasoning from the process calculi to state-machine languages would enable the specification of more complex systems and a more modular systems development process. Our insight is that we can recover many important results from the process calculi in hierarchical state machines with local scope. We employ a structural operational semantics, which is ubiquitous in process and 𝜆-calculi but uncommon in hierarchical statemachine formalizations, to enable inductive reasoning about behavior. Taking inspiration from the structure of process calculi metatheories, we define a calculus of refinement and equivalence that we prove sound with respect to local notion of (bi)simulation. Furthermore, we prove that the calculus preserves the behavioral properties of reactivity, observational determinism, traces, and linear temporal properties. Our results are mechanized in the Rocq proof assistant.