Perfect Half-Space Games
International audience We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional 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 bo...
Published in: | 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
---|---|
Main Authors: | , , , |
Other Authors: | , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2017
|
Subjects: | |
Online Access: | https://hal.science/hal-01633355 https://doi.org/10.1109/LICS.2017.8005105 |
id |
ftuniparissaclay:oai:HAL:hal-01633355v1 |
---|---|
record_format |
openpolar |
spelling |
ftuniparissaclay:oai:HAL:hal-01633355v1 2024-06-16T07:40:59+00:00 Perfect Half-Space Games Colcombet, Thomas Jurdzinski, Marcin Lazić, Ranko Schmitz, Sylvain Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Centre for Discrete Mathematics and its Applications Warwick (DIMAP) University of Warwick Coventry Department of Computer Science Warwick Laboratoire Spécification et Vérification Cachan (LSV) École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS) EPSRC grant EP/M011801/1 EPSRC grant EP/P020992/1 European Project: 259454,EC:FP7:ERC,ERC-2010-StG_20091028,GALE(2011) Reykjavik, Iceland 2017 https://hal.science/hal-01633355 https://doi.org/10.1109/LICS.2017.8005105 en eng HAL CCSD IEEE Press info:eu-repo/semantics/altIdentifier/arxiv/1704.05626 info:eu-repo/semantics/altIdentifier/doi/10.1109/LICS.2017.8005105 info:eu-repo/grantAgreement/EC/FP7/259454/EU/Games and Automata for Logic Extensions/GALE hal-01633355 https://hal.science/hal-01633355 ARXIV: 1704.05626 doi:10.1109/LICS.2017.8005105 Logic in Computer Science https://hal.science/hal-01633355 Logic in Computer Science, 2017, Reykjavik, Iceland. ⟨10.1109/LICS.2017.8005105⟩ [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] info:eu-repo/semantics/conferenceObject Conference papers 2017 ftuniparissaclay https://doi.org/10.1109/LICS.2017.8005105 2024-05-23T23:51:46Z International audience We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional 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 Jurdziński 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 Niwiński, 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 multi-dimensional 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. Conference Object Iceland Archives ouvertes de Paris-Saclay 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 1 11 |
institution |
Open Polar |
collection |
Archives ouvertes de Paris-Saclay |
op_collection_id |
ftuniparissaclay |
language |
English |
topic |
[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
spellingShingle |
[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Colcombet, Thomas Jurdzinski, Marcin Lazić, Ranko Schmitz, Sylvain Perfect Half-Space Games |
topic_facet |
[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
description |
International audience We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional 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 Jurdziński 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 Niwiński, 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 multi-dimensional 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. |
author2 |
Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Centre for Discrete Mathematics and its Applications Warwick (DIMAP) University of Warwick Coventry Department of Computer Science Warwick Laboratoire Spécification et Vérification Cachan (LSV) École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS) EPSRC grant EP/M011801/1 EPSRC grant EP/P020992/1 European Project: 259454,EC:FP7:ERC,ERC-2010-StG_20091028,GALE(2011) |
format |
Conference Object |
author |
Colcombet, Thomas Jurdzinski, Marcin Lazić, Ranko Schmitz, Sylvain |
author_facet |
Colcombet, Thomas Jurdzinski, Marcin Lazić, Ranko Schmitz, Sylvain |
author_sort |
Colcombet, Thomas |
title |
Perfect Half-Space Games |
title_short |
Perfect Half-Space Games |
title_full |
Perfect Half-Space Games |
title_fullStr |
Perfect Half-Space Games |
title_full_unstemmed |
Perfect Half-Space Games |
title_sort |
perfect half-space games |
publisher |
HAL CCSD |
publishDate |
2017 |
url |
https://hal.science/hal-01633355 https://doi.org/10.1109/LICS.2017.8005105 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Logic in Computer Science https://hal.science/hal-01633355 Logic in Computer Science, 2017, Reykjavik, Iceland. ⟨10.1109/LICS.2017.8005105⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/1704.05626 info:eu-repo/semantics/altIdentifier/doi/10.1109/LICS.2017.8005105 info:eu-repo/grantAgreement/EC/FP7/259454/EU/Games and Automata for Logic Extensions/GALE hal-01633355 https://hal.science/hal-01633355 ARXIV: 1704.05626 doi:10.1109/LICS.2017.8005105 |
op_doi |
https://doi.org/10.1109/LICS.2017.8005105 |
container_title |
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
container_start_page |
1 |
op_container_end_page |
11 |
_version_ |
1802008034444050432 |