Hyperplane separation technique for multidimensional mean-payoff games

作者：

Highlights：

• Pseudo-polynomial algorithm for finite-state fixed-dimensional mean-payoff games.

• One-player recursive multi-dimensional mean-payoff games in PTIME.

• Recursive one-dimensional mean-payoff games with constant parameters in PTIME.

摘要

•Pseudo-polynomial algorithm for finite-state fixed-dimensional mean-payoff games.•One-player recursive multi-dimensional mean-payoff games in PTIME.•Recursive one-dimensional mean-payoff games with constant parameters in PTIME.

论文关键词：Finite-state graph games,Mean-payoff objectives,Multidimensional objectives,Pushdown graphs and games,Computer-aided verification

论文评审过程：Received 4 May 2015, Revised 11 April 2017, Accepted 19 April 2017, Available online 4 May 2017, Version of Record 11 June 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.04.005