--- _id: '2246' abstract: - lang: eng text: 'Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. ' author: - first_name: Andrey full_name: Grinshpun, Andrey last_name: Grinshpun - first_name: Pakawat full_name: Phalitnonkiat, Pakawat last_name: Phalitnonkiat - first_name: Sasha full_name: Rubin, Sasha id: 2EC51194-F248-11E8-B48F-1D18A9856A87 last_name: Rubin - first_name: Andrei full_name: Tarfulea, Andrei last_name: Tarfulea citation: ama: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller and parity games. Theoretical Computer Science. 2014;521:73-91. doi:10.1016/j.tcs.2013.11.032 apa: Grinshpun, A., Phalitnonkiat, P., Rubin, S., & Tarfulea, A. (2014). Alternating traps in Muller and parity games. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2013.11.032 chicago: Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea. “Alternating Traps in Muller and Parity Games.” Theoretical Computer Science. Elsevier, 2014. https://doi.org/10.1016/j.tcs.2013.11.032. ieee: A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps in Muller and parity games,” Theoretical Computer Science, vol. 521. Elsevier, pp. 73–91, 2014. ista: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps in Muller and parity games. Theoretical Computer Science. 521, 73–91. mla: Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” Theoretical Computer Science, vol. 521, Elsevier, 2014, pp. 73–91, doi:10.1016/j.tcs.2013.11.032. short: A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer Science 521 (2014) 73–91. date_created: 2018-12-11T11:56:33Z date_published: 2014-02-13T00:00:00Z date_updated: 2021-01-12T06:56:16Z day: '13' department: - _id: KrCh doi: 10.1016/j.tcs.2013.11.032 intvolume: ' 521' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1303.3777 month: '02' oa: 1 oa_version: Submitted Version page: 73 - 91 publication: Theoretical Computer Science publication_identifier: issn: - '03043975' publication_status: published publisher: Elsevier publist_id: '4703' quality_controlled: '1' scopus_import: 1 status: public title: Alternating traps in Muller and parity games type: journal_article user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 521 year: '2014' ...