A cure for stuttering parity games

Onderzoeksoutput: Boek/rapportRapportAcademic

8 Citaten (Scopus)
89 Downloads (Pure)


We de¿ne governed stuttering bisimulation for parity games, weakening stuttering bisimulation by taking the ownership of vertices into account only when this might lead to observably different games. We show that governed stuttering bisimilarity is an equivalence for parity games and allows for a natural quotienting operation. Moreover, we prove that all pairs of vertices related by governed stuttering bisimilarity are won by the same player in the parity game. Thus, our equivalence can be used as a preprocessing step when solving parity games. Governed stuttering bisimilarity can be decided in O(n^2 m) time for parity games with n vertices and m edges. Our experiments indicate that governed stuttering bisimilarity is mostly competitive with stuttering equivalence on parity games encoding typical veri¿cation problems.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's25
StatusGepubliceerd - 2012

Publicatie series

NaamComputer science reports
ISSN van geprinte versie0926-4515

Vingerafdruk Duik in de onderzoeksthema's van 'A cure for stuttering parity games'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Cranen, S., Keiren, J. J. A., & Willemse, T. A. C. (2012). A cure for stuttering parity games. (Computer science reports; Vol. 1205). Technische Universiteit Eindhoven.