The Library
Perfect half space games
Tools
Tools
Tools
Colcombet, Thomas , Jurdzinski, Marcin, Lazic, Ranko and Schmitz, Sylvain (2017) Perfect half space games. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017. Published in: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) ISBN 9781509030187. doi:10.1109/LICS.2017.8005105
|
PDF
WRAP-Perfect-half-space-games-Lazic-2017.pdf - Accepted Version - Requires a PDF viewer. Download (759Kb) | Preview |
Official URL: http://lics.rwth-aachen.de/lics17/accepted.html
Abstract
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multidimensional weights diverge in a direction which is consistent with a chosen sequence of perfect half spaces (chosen dynamically by Player 2). We establish that the bounding games of Jurdzinski et al. (ICALP 2015) can be reduced to perfect half space games, which in turn can be translated to the lexicographic energy games of Colcombet and Niwinski, and are positionally determined in a strong sense (Player 2 can play without knowing the current perfect half space). We finally show how perfect half space games and bounding games can be employed to solve multidimensional energy parity games in pseudo-polynomial time when both the numbers of energy dimensions and of priorities are fixed, regardless of whether the initial credit is given as part of the input or existentially quantified. This also yields an optimal 2-EXPTIME complexity with given initial credit, where the best known upper bound was non-elementary.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Alternative Title: | |||||||
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Game theory , Computer science -- Mathematics | ||||||
| Series Name: | Annual Symposium on Logic in Computer Science | ||||||
| Journal or Publication Title: | Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||
| Publisher: | IEEE | ||||||
| ISBN: | 9781509030187 | ||||||
| Official Date: | 18 August 2017 | ||||||
| Dates: |
|
||||||
| DOI: | 10.1109/LICS.2017.8005105 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 21 April 2017 | ||||||
| Date of first compliant Open Access: | 25 April 2017 | ||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC) | ||||||
| Grant number: | EP/M011801/1, EP/P020992/1 (EPSRC), 259454 (GALE) (ERC) | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Reykjavik, Iceland | ||||||
| Date(s) of Event: | 20-23 Jun 2017 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
