I would like to understand the ideas behind parity games and their winning conditions. Where do they come from?

  • 2
    $\begingroup$ This is a very general question. Can you be more specific? Which ideas are you interested in? What kind of answer are you hoping for? $\endgroup$ – Yuval Filmus Aug 1 '16 at 20:12
  • $\begingroup$ I read this question as follows: The OP wants to get a general overview about what parity games are and what they are good for. "Where do they come from?" does not mean their history, but is rather a request for a step-by-step introduction into how they are motivated by some (example) application. I think that the scientific papers "out there" do a poor job in this regard, and even text books (such as LNCS 2500) are not great either (they jump relatively straight to the formal definitions). The question can be understood as a request for a reference to a self-contained paper. $\endgroup$ – DCTLib Aug 2 '16 at 8:38
  • $\begingroup$ Thank you DCTLib. I also have more specific questions but as you say scientific papers always start with formal definitions. Why should someone come up with a game in which one player wins if the lowest priority that occurs infinitely often is even? $\endgroup$ – Alberto Aug 2 '16 at 9:06
  • $\begingroup$ @Alberto One reason is solving parity games turns out to be equivalent to solving modal $\mu$-calculus, which is useful in model checking, see also wikipedia. $\endgroup$ – Discrete lizard Feb 25 '17 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.