Eprint already available on another site (E-prints, Working papers and Research blog)
A positional Π^0_3-complete objective
Casares, Antonio; Ohlmann, Pierre; Vandenhove, Pierre
2024
 

Files


Full Text
2410.14688v1.pdf
Author preprint (611.82 kB) Creative Commons License - Attribution
Download

All documents in ORBi UMONS are protected by a user license.

Send to



Details



Abstract :
[en] We study zero-sum turn-based games on graphs. In this note, we show the existence of a game objective that is $\Pi^0_3$-complete for the Borel hierarchy and that is positional, i.e., for which positional strategies suffice for the first player to win over arenas of arbitrary cardinality. To the best of our knowledge, this is the first known such objective; all previously known positional objectives are in $\Sigma^0_3$. The objective in question is a qualitative variant of the well-studied total-payoff objective, where the goal is to maximise the sum of weights.
Research center :
CREMMI - Modélisation mathématique et informatique
Disciplines :
Computer science
Mathematics
Author, co-author :
Casares, Antonio;  University of Warsaw [PL]
Ohlmann, Pierre;  AMU - Aix-Marseille Université [FR]
Vandenhove, Pierre  ;  Université de Mons - UMONS > Faculté des Sciences > Service d'Informatique théorique ; Université de Bordeaux [FR] > LaBRI
Language :
English
Title :
A positional Π^0_3-complete objective
Publication date :
October 2024
Publisher :
ArXiv
Number of pages :
7
Research unit :
S829 - Informatique théorique
Research institute :
Complexys
Infortech
Funders :
ANR - Agence Nationale de la Recherche
NCN - National Science Centre Poland
Funding text :
Antonio Casares is funded by the Polish National Science Centre (NCN) grant Polynomial finite state computation (2022/46/A/ST6/00072). Pierre Vandenhove is funded by ANR project G4S (ANR-21-CE48-0010-01).
Commentary :
7 pages, 1 figure
Available on ORBi UMONS :
since 03 December 2024

Statistics


Number of views
14 (1 by UMONS)
Number of downloads
6 (0 by UMONS)

Bibliography


Similar publications



Contact ORBi UMONS