Geodesic
Exponential examples of solving parity games
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 4, pp. 694-703

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {56},
     number = {4},
     year = {2016},
     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
PB  - mathdoc
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
%I mathdoc
%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/