Benjamin Plummer ; Corina Cirstea - Traces via Strategies in Two-Player Games

entics:16816 - Electronic Notes in Theoretical Informatics and Computer Science, December 20, 2025, Volume 5 - Proceedings of MFPS XLI - https://doi.org/10.46298/entics.16816
Traces via Strategies in Two-Player GamesArticle

Authors: Benjamin Plummer ; Corina Cirstea

    Traces form a coarse notion of semantic equivalence between states of a process, and have been studied coalgebraically for various types of system. We instantiate the finitary coalgebraic trace semantics framework of Hasuo et al. for controller-versus-environment games, encompassing both nondeterministic and probabilistic environments. Although our choice of monads is guided by the constraints of this abstract framework, they enable us to recover familiar game-theoretic concepts. Concretely, we show that in these games, each element in the trace map corresponds to a collection (a subset or distribution) of plays the controller can force. Furthermore, each element can be seen as the outcome of following a controller strategy. Our results are parametrised by a weak distributive law, which computes what the controller can force in a single step.


    Volume: Volume 5 - Proceedings of MFPS XLI
    Published on: December 20, 2025
    Accepted on: October 29, 2025
    Submitted on: October 29, 2025
    Keywords: Logic in Computer Science