Geodesic
Exponential examples of solving parity games
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 4, pp. 694-703 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is devoted to solving certain problems on the computational complexity of deciding the winner in cyclic games. The main result is the proof of the fact that the nondeterministic potential transformation algorithm designed for solving parity games is exponential in terms of computation time. 
@article{ZVMMF_2016_56_4_a13,
     author = {V. N. Lebedev},
     title = {Exponential examples of solving parity games},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {694--703},
     year = {2016},
     volume = {56},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a13/}
}
TY  - JOUR
AU  - V. N. Lebedev
TI  - Exponential examples of solving parity games
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 694
EP  - 703
VL  - 56
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a13/
LA  - ru
ID  - ZVMMF_2016_56_4_a13
ER  - 
%0 Journal Article
%A V. N. Lebedev
%T Exponential examples of solving parity games
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 694-703
%V 56
%N 4
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a13/
%G ru
%F ZVMMF_2016_56_4_a13
V. N. Lebedev. Exponential examples of solving parity games. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 4, pp. 694-703. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a13/

[1] Gurvich V. A., Karzanov A. V., Khachiyan L. G., “Tsiklicheskie igry i algoritm nakhozhdeniya minimaksnykh srednikh tsiklov v orientirovannykh grafakh”, Zh. vychisl. matem. i matem. fiz., 28:5 (1988), 85–91 | MR | Zbl

[2] Pisaruk N., “Mean cost cyclical games”, Math. Operat. Research, 59:4 (1999), 817–828 | DOI | MR

[3] Karzanov A. V., Lebedev V. N., “Cyclical games with prohibitions”, Math. Program., 60 (1993), 277–293 | DOI | MR | Zbl

[4] Jurdzinski M., “Deciding the winner in parity games is in $UP\cap co-UP$”, Informat. Proc. Letters, 68 (1998), 119–124 | DOI | MR

[5] Beffara E., Vorobyov S., Is randomized Gurvich–Karzanov–Khachiyan's algorithm for parity games polynomial?, Technical report, Department of information Technology Uppsala University, 2001