Parity to safety in polynomial time for pushdown and collapsible pushdown systems

Hague, M ORCID: 0000-0003-4913-3800, Meyer, R, Muskalla, S ORCID: 0000-0001-9195-7323 and Zimmermann, M ORCID: 0000-0002-8038-2453 (2018) Parity to safety in polynomial time for pushdown and collapsible pushdown systems. .

Text
LIPIcs-MFCS-2018-57.pdf - Published version
Download (476kB) | Preview

Official URL: http://www.dagstuhl.de/dagpub/978-3-95977-086-6

Abstract

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.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	12 Jul 2019 14:51
Last Modified:	24 Nov 2023 07:21
DOI:	10.4230/LIPIcs.MFCS.2018.57
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3049666