A cure for stuttering parity games

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)
1 Downloads (Pure)


We define 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(n2m)(n2m) 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 verification problems.
Originele taal-2Engels
TitelTheoretical Aspects of Computing – ICTAC 2012 (9th International Colloquium, Bangalore, India, September 24-27, 2012. Proceedings)
RedacteurenA. Roychoudhury, M. D'Souza
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-32942-5
StatusGepubliceerd - 2012
Evenement9th International Colloquium on Theoretical Aspects of Computing (ICTAC 2012) - Bangalore, India
Duur: 24 sep 201227 sep 2012
Congresnummer: 9

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres9th International Colloquium on Theoretical Aspects of Computing (ICTAC 2012)
Verkorte titelICTAC 2012
Ander9th International Colloquium on Theoretical Aspects of Computing

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

Citeer dit