A Formal Framework of Model and Logical Embeddings for Verification of Stochastic Systems

This paper proposes a formal framework for minimizing, analyzing and verifying stochastic process algebraic models using tools and techniques developed for the state-labeled domain, and vice versa. First, we modify the model embeddings proposed in the literature between action-labeled continuous-time Markov chains (ACTMCs) and state-labeled continuous-time Markov chains (SCTMCs), and show that our modified model embeddings do not create unreachable states in the embedded model and preserve several equivalence relations of interest, e.g., strong forward bisimulation, strong backward bisimulation and weak forward bisimulation. Next, we propose the syntax and semantics of an action-based continuous stochastic logic (ACSL) interpreted over action-labeled continuous-time Markov chains (ACTMCs). We define an embedding atsl which can be used to construct a continuous stochastic logic (CSL) formula from an ACSL formula, an embedding stal from CSL \ X to ACSL \ {Xχ,Xτ}, and an embedding stal′ from CSL to ACSL. We prove that ACSL model checking can be reduced to CSL model checking and vice versa when the model embeddings are not sensitive to the invisible computation steps. Similarly, we prove that ACSL \ {Xχ, Xτ} model checking can be reduced to CSL \ X model checking when the model embeddings are sensitive to the invisible computation steps. In order to validate the efficacy and usefulness of this framework, we have applied it to several interesting case studies from the stochastic process algebraic setting. Our experimental results show that this framework enables one to model check ACTMC models which otherwise cannot be verified using the well-known tools available in the action-labeled domain.