Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems. / Hague, Matthew; Meyer, Roland; Muskalla, Sebastian; Zimmermann, Martin.

International Symposium of Mathematical Foundations of Computer Science. 2018. p. 1-15 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 117).

Research output: Chapter in Book/Report/Conference proceedingConference contribution



We give a direct polynomial-time reduction from parity games played over the configuration graphs of collapsible pushdown systems to safety games played over the same class of graphs. That a polynomial-time reduction would exist was known since both problems are complete for the same complexity class. Coming up with a direct reduction, however, has been an open problem. Our solution to the puzzle brings together a number of techniques for pushdown games and adds three new ones. This work contributes to a recent trend of liveness to safety reductions which allow the advanced state-of-the-art in safety checking to be used for more expressive specifications.
Original languageEnglish
Title of host publicationInternational Symposium of Mathematical Foundations of Computer Science
Number of pages15
Publication statusPublished - 20 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 30819149