2026-07-26T17:23:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19374 2024-03-06T11:03:52Z ddc:004 open_access

Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity (Invited Talk) Brihaye, Thomas Goeminne, Aline Main, James C. A. Randour, Mickael Games on graphs reachability finite-memory strategies complexity Reachability objectives are arguably the most basic ones in the theory of games on graphs (and beyond). But far from being bland, they constitute the cornerstone of this field. Reachability is everywhere, as are the tools we use to reason about it. In this invited contribution, we take the reader on a journey through a zoo of models that have reachability objectives at their core. Our goal is to illustrate how model complexity impacts the complexity of strategies needed to play optimally in the corresponding games and computational complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Brihaye and Aline Goeminne and James C. A. Main and Mickael Randour 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.1 urn:nbn:de:0030-drops-193747 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.1 eng https://creativecommons.org/licenses/by/4.0/legalcode