Skip to main content

Questions tagged [game-semantics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
184 views

Understanding a proof from a paper (model checking game)

I'm reading the paper: "Model Checking Games for Branching Time Logics" by Martin Lange and Colin Stirling - https://carrick.fmv.informatik.uni-kassel.de/~mlange/papers/jlc2000.pdf. The ...
Mcgfbtl's user avatar
  • 41
2 votes
1 answer
297 views

Complexity of parity game solving compared to PLS, PPA, and PPAD

Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or ...
Thomas Klimpel's user avatar
3 votes
1 answer
70 views

What's the correct definition of the $\Upsilon$ category of schedules?

I'm reading this article about game semantics and I'm a bit puzzled with the definition given for $\Upsilon$ in section $3.3$. There are some points that are either unintelligible or that don't make ...
Bakuriu's user avatar
  • 807
3 votes
0 answers
62 views

How to prove that the composite strategy is prefix-closed and respects the alternation condition?

I'm doing some research on game semantics using these notes. Currently I'm trying to prove that the definition of composite-strategy is indeed a strategy. I have already proved all the conditions of ...
Bakuriu's user avatar
  • 807