Distribution-Based Behavioral Distance for Nondeterministic Fuzzy Transition Systems

Abstract

Modal logics and behavioral equivalences play an important role in the specification and verification of concurrent systems. In this paper, we first present a new notion of bisimulation for nondeterministic fuzzy transition systems, which is distribution based and coarser than state-based bisimulation appeared in the literature. Then, we define a distribution-based bisimilarity metric as the least fixed point of a suitable monotonic function on a complete lattice, which is a behavioral distance and is a more robust way of formalizing behavioral similarity between states than bisimulations. We also propose an on-the-fly algorithm for computing the bisimilarity metric. Moreover, we present a fuzzy modal logic and provide a sound and complete characterization of the bisimilarity metric. Interestingly, this characterization holds for a class of fuzzy modal logics. In addition, we show the nonexpansiveness of a typical parallel composition operator with respect to the bisimilarity metric, which makes compositional verification possible.