Divide and congruence: From decomposition of modalities to preservation of branching bisimulation

Abstract

We present a method for decomposing modal formulas for processes with the internal action tau. To decide whether a process algebra term satisfies a modal formula, one can check whether its subterms satisfy formulas that are obtained by decomposing the original formula. The decomposition uses the structural operational semantics that underlies the process algebra. We use this decomposition method to derive congruence formats for branching and rooted branching bisimulation equivalence.