{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:20:35Z","timestamp":1781893235251,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T00:00:00Z","timestamp":1499904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["C252-000-087-001"],"award-info":[{"award-number":["C252-000-087-001"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M027287\/1 and EP\/P020909\/1"],"award-info":[{"award-number":["EP\/M027287\/1 and EP\/P020909\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["Academic Research Fund Tier 2 grant MOE2016-T2-1-019 \/ R146-000-234-112"],"award-info":[{"award-number":["Academic Research Fund Tier 2 grant MOE2016-T2-1-019 \/ R146-000-234-112"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,7,13]]},"DOI":"10.1145\/3092282.3092286","type":"proceedings-article","created":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T13:45:49Z","timestamp":1499953549000},"page":"112-121","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["An ordered approach to solving parity games in quasi polynomial time and quasi linear space"],"prefix":"10.1145","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[{"name":"University of Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Schewe","sequence":"additional","affiliation":[{"name":"University of Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[{"name":"University of Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,7,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_3_2_1_2_1","unstructured":"Dietmar Berwanger Anuj Dawar Paul Hunter and Stephan Kreutzer. 2006.  Dietmar Berwanger Anuj Dawar Paul Hunter and Stephan Kreutzer. 2006."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_43"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.029"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00228-9"},{"key":"e_1_3_2_1_6_1","unstructured":"Cristian S. Calude Sanjay Jain Bakhadyr Khoussainov Wei Li and Frank Stephan. 2017.  Cristian S. Calude Sanjay Jain Bakhadyr Khoussainov Wei Li and Frank Stephan. 2017."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055409"},{"key":"e_1_3_2_1_8_1","unstructured":"Krishnendu Chatterjee Monika Henzinger and Veronika Loitzenbauer. 2015.  Krishnendu Chatterjee Monika Henzinger and Veronika Loitzenbauer. 2015."},{"key":"e_1_3_2_1_9_1","volume-title":"Proc. of LICS. IEEE Computer Society, 269\u2013280","author":"Improved Algorithms","unstructured":"Improved Algorithms for One-Pair and k-Pair Streett Objectives . In Proc. of LICS. IEEE Computer Society, 269\u2013280 . Improved Algorithms for One-Pair and k-Pair Streett Objectives. In Proc. of LICS. IEEE Computer Society, 269\u2013280."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2001.932504"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_3_2_1_12_1","unstructured":"E. Allen Emerson Charanjit S. Jutla and A. Prasad Sistla. 1993.  E. Allen Emerson Charanjit S. Jutla and A. Prasad Sistla. 1993."},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. of CAV. 385\u2013396","author":"On","unstructured":"On Model-Checking for Fragments of \u00b5-Calculus .. In Proc. of CAV. 385\u2013396 . On Model-Checking for Fragments of \u00b5-Calculus.. In Proc. of CAV. 385\u2013396."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. of LICS. IEEE Computer Society Press, 267\u2013278","author":"Allen Emerson E.","unstructured":"E. Allen Emerson and C. Lei . 1986. Efcient model checking in fragments of the propositional \u00b5-calculus . In Proc. of LICS. IEEE Computer Society Press, 267\u2013278 . E. Allen Emerson and C. Lei. 1986. Efcient model checking in fragments of the propositional \u00b5-calculus. In Proc. of LICS. IEEE Computer Society Press, 267\u2013278."},{"key":"e_1_3_2_1_15_1","unstructured":"John Fearnley. 2010.  John Fearnley. 2010."},{"key":"e_1_3_2_1_16_1","volume-title":"Strategy Improvement. In Proc. of LPAR. 212\u2013230","unstructured":"Non-oblivious Strategy Improvement. In Proc. of LPAR. 212\u2013230 . Non-oblivious Strategy Improvement. In Proc. of LPAR. 212\u2013230."},{"key":"e_1_3_2_1_17_1","volume-title":"An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms. LMCS 7, 3","author":"Friedmann Oliver","year":"2011","unstructured":"Oliver Friedmann . 2011. An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms. LMCS 7, 3 ( 2011 ). Oliver Friedmann. 2011. An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms. LMCS 7, 3 (2011)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011124"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04761-9_15"},{"key":"e_1_3_2_1_20_1","unstructured":"Oliver Friedmann and Martin Lange. 2014.  Oliver Friedmann and Martin Lange. 2014."},{"key":"e_1_3_2_1_21_1","volume-title":"University of Munich","author":"The","year":"2014","unstructured":"The PGSolver collection of parity game solvers. University of Munich ( 2014 ). http:\/\/www.win.tue.nl\/ timw\/downloads\/amc2014\/pgsolver.pdf. The PGSolver collection of parity game solvers. University of Munich (2014). http:\/\/www.win.tue.nl\/ timw\/downloads\/amc2014\/pgsolver.pdf."},{"key":"e_1_3_2_1_22_1","volume-title":"https: \/\/github.com\/tcsprojects\/pgsolver","author":"Friedmann Oliver","year":"2017","unstructured":"Oliver Friedmann and Martin Lange . 2017. PG Solver Version 4.0. ( 2017 ). https: \/\/github.com\/tcsprojects\/pgsolver Oliver Friedmann and Martin Lange. 2017. PGSolver Version 4.0. (2017). https: \/\/github.com\/tcsprojects\/pgsolver"},{"key":"e_1_3_2_1_23_1","unstructured":"Ernst Moritz Hahn Sven Schewe Andrea Turrini and Lijun Zhang. 2016.  Ernst Moritz Hahn Sven Schewe Andrea Turrini and Lijun Zhang. 2016."},{"key":"e_1_3_2_1_24_1","volume-title":"Simple Algorithm for Solving Qualitative Probabilistic Parity Games. In Proc. of CAV (LNCS)","volume":"9780","author":"A","unstructured":"A Simple Algorithm for Solving Qualitative Probabilistic Parity Games. In Proc. of CAV (LNCS) , Vol. 9780 . 291\u2013311. A Simple Algorithm for Solving Qualitative Probabilistic Parity Games. In Proc. of CAV (LNCS), Vol. 9780. 291\u2013311."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_3_2_1_26_1","volume-title":"Proc","author":"Marcin Jurdzi","unstructured":"Marcin Jurdzi \u00b4 nski. 2000. Small progress measures for solving parity games . In Proc . of STACS. Springer-Verlag , 290\u2013301. Marcin Jurdzi \u00b4 nski. 2000. Small progress measures for solving parity games. In Proc. of STACS. Springer-Verlag, 290\u2013301."},{"key":"e_1_3_2_1_27_1","volume-title":"Proc. of LICS","author":"Ranko Marcin Jurdzi","year":"2017","unstructured":"Marcin Jurdzi \u00b4 nski and Ranko Lazi\u00b4 c. 2017 . Succinct progress measures for solving parity games . In Proc. of LICS 2017. (to appear). https:\/\/arxiv.org\/abs\/1702.05051 Marcin Jurdzi \u00b4 nski and Ranko Lazi\u00b4 c. 2017. Succinct progress measures for solving parity games. In Proc. of LICS 2017. (to appear). https:\/\/arxiv.org\/abs\/1702.05051"},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. of SODA. ACM\/SIAM, 117\u2013123","author":"M. Jurdzi","unstructured":"M. Jurdzi \u00b4 nski, M. Paterson , and U. Zwick . 2006. A Deterministic Subexponential Algorithm for Solving Parity Games . In Proc. of SODA. ACM\/SIAM, 117\u2013123 . M. Jurdzi \u00b4 nski, M. Paterson, and U. Zwick. 2006. A Deterministic Subexponential Algorithm for Solving Parity Games. In Proc. of SODA. ACM\/SIAM, 117\u2013123."},{"key":"e_1_3_2_1_29_1","unstructured":"Dexter Kozen. 1983.  Dexter Kozen. 1983."},{"key":"e_1_3_2_1_30_1","volume-title":"333\u2013354","author":"Calculus Results","year":"1983","unstructured":"Results on the Propositional \u00b5- Calculus . TCS 27 ( 1983 ), 333\u2013354 . Results on the Propositional \u00b5-Calculus. TCS 27 (1983), 333\u2013354."},{"key":"e_1_3_2_1_31_1","unstructured":"M. Lange. 2005.  M. Lange. 2005."},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. of Int. Workshop on Games in Design and Verification.","author":"Parity Solving","unstructured":"Solving Parity Games by a Reduction to SAT . In Proc. of Int. Workshop on Games in Design and Verification. Solving Parity Games by a Reduction to SAT. In Proc. of Int. Workshop on Games in Design and Verification."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1035"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"e_1_3_2_1_35_1","unstructured":"Jan Obdr\u02c7 z \u00e1lek. 2003.  Jan Obdr\u02c7 z \u00e1lek. 2003."},{"key":"e_1_3_2_1_36_1","volume-title":"Proc","author":"Model Fast","unstructured":"Fast Mu-calculus Model Checking when Tree-width is Bounded . In Proc . of CAV. Springer-Verlag , 80\u201392. Fast Mu-calculus Model Checking when Tree-width is Bounded. In Proc. of CAV. Springer-Verlag, 80\u201392."},{"key":"e_1_3_2_1_37_1","unstructured":"Nir Piterman. 2006.  Nir Piterman. 2006."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.28"},{"key":"e_1_3_2_1_39_1","unstructured":"Anuj Puri. 1995.  Anuj Puri. 1995."},{"key":"e_1_3_2_1_40_1","volume-title":"Computer Science Department","author":"Ph Theory","unstructured":"Theory of hybrid systems and discrete event systems. Ph . D. Dissertation . Computer Science Department , University of California , Berkeley. Theory of hybrid systems and discrete event systems. Ph.D. Dissertation. Computer Science Department, University of California, Berkeley."},{"key":"e_1_3_2_1_41_1","unstructured":"Ash B. Robert. 1990. Information Theory. (1990).  Ash B. Robert. 1990. Information Theory. (1990)."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87531-4_27"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.10.002"},{"key":"e_1_3_2_1_44_1","volume-title":"Proc","author":"Schewe Sven","unstructured":"Sven Schewe and Bernd Finkbeiner . 2006. The Alternating-Time \u00b5-calculus and Automata over Concurrent Game Structures . In Proc . of CSL. Springer-Verlag , 591\u2013605. Sven Schewe and Bernd Finkbeiner. 2006. The Alternating-Time \u00b5-calculus and Automata over Concurrent Game Structures. In Proc. of CSL. Springer-Verlag, 591\u2013605."},{"key":"e_1_3_2_1_45_1","volume-title":"Proc","author":"Schewe Sven","unstructured":"Sven Schewe and Bernd Finkbeiner . 2006. Synthesis of Asynchronous Systems . In Proc . of LOPSTR. Springer-Verlag , 127\u2013142. Sven Schewe and Bernd Finkbeiner. 2006. Synthesis of Asynchronous Systems. In Proc. of LOPSTR. Springer-Verlag, 127\u2013142."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_31"},{"key":"e_1_3_2_1_47_1","unstructured":"Patrick Totzke. 2017. Implementation of the succinct progress measures algorithm from {20}. (2017). https:\/\/github.com\/pazz\/pgsolver\/tree\/sspm  Patrick Totzke. 2017. Implementation of the succinct progress measures algorithm from {20}. (2017). https:\/\/github.com\/pazz\/pgsolver\/tree\/sspm"},{"key":"e_1_3_2_1_48_1","volume-title":"Proc","author":"Vardi Moshe Y.","unstructured":"Moshe Y. Vardi . 1998. Reasoning about The Past with Two-Way Automata . In Proc . of ICALP. Springer-Verlag , 628\u2013641. Moshe Y. Vardi. 1998. Reasoning about The Past with Two-Way Automata. In Proc. of ICALP. Springer-Verlag, 628\u2013641."},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. of the","author":"\u00f6ge Jens V","unstructured":"Jens V \u00f6ge and Marcin Jurdzi \u00b4 nski. 2000. A Discrete Strategy Improvement Algorithm for Solving Parity Games . In Proc. of the CAV. Springer-Verlag , 202\u2013215. Jens V \u00f6ge and Marcin Jurdzi \u00b4 nski. 2000. A Discrete Strategy Improvement Algorithm for Solving Parity Games. In Proc. of the CAV. Springer-Verlag, 202\u2013215."},{"key":"e_1_3_2_1_50_1","unstructured":"Thomas Wilke. 2001.  Thomas Wilke. 2001."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Alternating Tree Automata Parity Games and Modal \u00b5-Calculus. Bull. Soc. Math. Belg. 8 2 (May 2001).  Alternating Tree Automata Parity Games and Modal \u00b5-Calculus. Bull. Soc. Math. Belg. 8 2 (May 2001).","DOI":"10.36045\/bbms\/1102714178"},{"key":"e_1_3_2_1_52_1","unstructured":"Wieslaw Zielonka. 1998.  Wieslaw Zielonka. 1998."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00009-7"}],"event":{"name":"ISSTA '17: International Symposium on Software Testing and Analysis","location":"Santa Barbara CA USA","acronym":"ISSTA '17","sponsor":["SIGSOFT ACM Special Interest Group on Software Engineering"]},"container-title":["Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092282.3092286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3092282.3092286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:08Z","timestamp":1750215788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092282.3092286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,13]]},"references-count":53,"alternative-id":["10.1145\/3092282.3092286","10.1145\/3092282"],"URL":"https:\/\/doi.org\/10.1145\/3092282.3092286","relation":{},"subject":[],"published":{"date-parts":[[2017,7,13]]},"assertion":[{"value":"2017-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}