Stephan Spengler ; Sanchari Sil
-
TSO Games -- On the decidability of safety games under the total store order semantics (extended LMCS version with appendix)
lmcs:13261 -
Logical Methods in Computer Science,
September 24, 2025,
Volume 21, Issue 3
-
https://doi.org/10.46298/lmcs-21(3:30)2025TSO Games -- On the decidability of safety games under the total store order semantics (extended LMCS version with appendix)Article
Authors: Stephan Spengler ; Sanchari Sil
NULL##NULL
Stephan Spengler;Sanchari Sil
We consider an extension of the classical Total Store Order (TSO) semantics by expanding it to turn-based 2-player safety games. During her turn, a player can select any of the communicating processes and perform its next transition. We consider different formulations of the safety game problem depending on whether one player or both of them transfer messages from the process buffers to the shared memory. We give the complete decidability picture for all the possible alternatives.
Volume: Volume 21, Issue 3
Published on: September 24, 2025
Accepted on: June 30, 2025
Submitted on: March 21, 2024
Keywords: Computer Science and Game Theory