Reachability in Fuzzy Game Graphs

doi:10.1109/TFUZZ.2016.2593495

CORC > 北京大学 > 信息科学技术学院

	Reachability in Fuzzy Game Graphs
	Pan, Haiyu ; Li, Yongming ; Cao, Yongzhi ; Li, Dechao
刊名	IEEE TRANSACTIONS ON FUZZY SYSTEMS
	2017
关键词	Fuzzy automaton fuzzy logic fuzzy transition system (FTS) game graph reachability DISCRETE-EVENT SYSTEMS COMPUTATION TREE LOGIC OMEGA-REGULAR GAMES MODEL CHECKING TRANSITION-SYSTEMS SUPERVISORY CONTROL FINITE AUTOMATA MOBILE ROBOT APPROXIMATION SIMULATION
DOI	10.1109/TFUZZ.2016.2593495
英文摘要	Two-player turn-based games on graphs (or game graphs for short) and their probabilistic versions have received increasing attention in computer science, especially in the formal verification of reactive systems. However, in the fuzzy setting, game graphs are yet to be addressed, although some practical applications, such as modeling fuzzy systems that interact with their environments, appeal to such models. To fill the gap, in this paper, we propose a fuzzy version of game graphs and focus on the fuzzy game graphs with reachability objectives, which we will refer to as fuzzy reachability games (FRGs). In an FRG, the goal of one player is tomaximize her truth value of reaching a given target set, while the other player aims at the opposite. In this framework, we show that FRGs are determined in the sense that for every state, both of the two players have the same value, and there exist optimal memoryless strategies for both players. Moreover, we design algorithms, which achieve polynomial time complexity in the size of the FRG, to compute the values of all states and the optimal memoryless strategies for the players. For a special class of FRGs, we provide an improved algorithm that achieves linear-logarithmic running time to compute the values of states. In addition, several examples are given to illustrate our motivation and the theoretical development.; National Natural Science Foundation of China [11271237, 61228305, 61370053, 11301321, 11401361, 61672023]; Higher School Doctoral Subject Foundation of the Ministry of Education of China [20130202110001]; China Postdoctoral Science Foundation [2014M552408]; SCI(E); ARTICLE; 4; 972-984; 25
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/471813]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Pan, Haiyu,Li, Yongming,Cao, Yongzhi,et al. Reachability in Fuzzy Game Graphs[J]. IEEE TRANSACTIONS ON FUZZY SYSTEMS,2017.
APA	Pan, Haiyu,Li, Yongming,Cao, Yongzhi,&Li, Dechao.(2017).Reachability in Fuzzy Game Graphs.IEEE TRANSACTIONS ON FUZZY SYSTEMS.
MLA	Pan, Haiyu,et al."Reachability in Fuzzy Game Graphs".IEEE TRANSACTIONS ON FUZZY SYSTEMS (2017).