Metraipolis › archive › dc_3fd489a1190d
Antichains for Concurrent Parameterized Games — arXiv:2610.11711
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.11711
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:36:28.315Z
- SHA-256 of the archived text
3b3c1276c108d64004d6edb600485cd89fdb8fb3ca21e31bd27bea7cc0fec609- Stable URL of this page
https://metraipolis.com/documento/dc_3fd489a1190d
How to cite
Antichains for Concurrent Parameterized Games — arXiv:2610.11711 — arXiv (en), https://arxiv.org/abs/2610.11711 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3fd489a1190d (Metraipolis archive dc_3fd489a1190d, sha256 3b3c1276c108d64004d6edb600485cd89fdb8fb3ca21e31bd27bea7cc0fec609)
BibTeX
@misc{dc3fd489a1190d,
title = {Antichains for Concurrent Parameterized Games — arXiv:2610.11711},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.11711},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3fd489a1190d; sha256 3b3c1276c108d64004d6edb600485cd89fdb8fb3ca21e31bd27bea7cc0fec609},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11711. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno). Categorie arXiv: Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2610.11711 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:57:16.305Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).