Permissive strategies: From parity games to safety games

被引：52

作者：

Bernet, J ^{[1
]}

Janin, D ^{[1
]}

Walukiewicz, I ^{[1
]}

机构：

[1] Univ Bordeaux 1, CNRS, LaBRI, F-33405 Talence, France

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2002年 / 36卷 / 03期

关键词：

D O I：

10.1051/ita:2002013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler problem of finding the set of winning positions in a parity game. The algorithm can be seen as a reduction of a parity to a safety game and computation of the set of winning positions in the resulting game.

引用

页码：261 / 275

页数：15

共 21 条

[1]

[Anonymous], HDB FORMAL LANGUAGES

[2]

[Anonymous], HDB THEORETICAL COMP

[3]

ARNOLD A, IN PRESS THEORET COM

[4] A UNIFIED APPROACH TO CONTROL-PROBLEMS IN DISCRETE-EVENT PROCESSES [J].

BERGERON, A .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1993, 27 (06) :555-573

[5] STATE-STRATEGIES FOR GAMES IN F-SIGMA-DELTA INTERSECTION G-DELTA-SIGMA [J].

BUCHI, JR .

JOURNAL OF SYMBOLIC LOGIC, 1983, 48 (04) :1171-1198

[6]

Cassandras C. G., 2009, Introduction to discrete event systems, V2nd, DOI 10.1007/978-3-030-72274-6

[7]

Dziembowski S., 1997, LICS 97, P99

[8]

EMERSON EA, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P368, DOI 10.1109/SFCS.1991.185392

[9]

EMERSON EA, 1993, LECT NOTES COMPUT SC, V697, P385, DOI DOI 10.1007/3-540-56922-7_32

[10]

GRUMBERG O, 2001, LECT NOTES COMPUT SC, V2102

← 1 2 3 →