文章基本信息

标题：Explicit Muller Games are PTIME
本地全文：下载
作者：Florian Horn
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：235-243
DOI：10.4230/LIPIcs.FSTTCS.2008.1756
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Regular games provide a very useful model for the synthesis of controllers in reactive systems. The complexity of these games depends on the representation of the winning condition: if it is represented through a win-set, a coloured condition, a Zielonka-DAG or Emerson-Lei formulae, the winner problem is \pspace-complete; if the winning condition is represented as a Zielonka tree, the winner problem belongs to \np and \conp. In this paper, we show that explicit Muller games can be solved in polynomial time, and provide an effective algorithm to compute the winning regions.
关键词：Games; authomata; model checking