Alternating refinement relations for fuzzy concurrent game structures

Fuzzy concurrent game structures (FCGSs), an extension of concurrent game structures in the fuzzy setting, combine both fuzzy and nondeterministic choices. They are therefore a powerful semantic foundation for modeling fuzzy systems that interact with their environments. In recent years, refinement relations in the field of formal verification, including trace containment and simulation, have been successfully introduced to special classes or related ones of FCGSs, such as fuzzy transition systems and fuzzy automata, and have been developed. However, these refinement relations are not directly applicable to FCGSs as they constrain the possible behaviors of the environment. To further satisfy the need for analysis and verification of fuzzy systems, this paper introduces alternating refinement relations for FCGSs. First, we present two general notions of alternating trace containment for FCGSs. Although these notions coincide with the corresponding classical ones, they do not coincide for FCGSs. Then, we provide algorithms to solve the problems of deciding two types of alternating trace containments in finite FCGSs under memoryless strategies. On the other hand, we propose two types of alternating simulations for FCGSs via weight functions and closed sets, and discover a novel result that they have different discriminating power, with one alternating simulation implying the other. Finally, we investigate the relationships among these notions mentioned above.

Authors

• Shasha Zhang
• Jie Zhou East China Normal University
• Yanfang Ma
• Haiyu Pan

Keywords

• Alternating simulation
• Fuzzy language
• Bisimulation
• Fuzzy automata