Parity Games of Bounded Tree- and Clique-Width

详细信息    查看全文

• 作者：Moses Ganardi (14)
  
  14. University of Siegen ; Siegen ; Germany
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9034
• 期：1
• 页码：390-404
• 全文大小：271 KB
• 参考文献：1. Stirling, C. Local model checking games. In: Lee, I., Smolka, S.A. eds. (1995) CONCUR 鈥?5 Concurrency Theory. Springer, Heidelberg, pp. 1-11 CrossRef
  2. Jurdzi艅ski, M. (1998) Deciding the winner in parity games is in UP 鈭?co-UP. Information Processing Letters 68: pp. 119-124 CrossRef
  3. Obdr啪谩lek, J. Fast mu-calculus model checking when tree-width is bounded. In: Hunt, W.A., Somenzi, F. eds. (2003) Computer Aided Verification. Springer, Heidelberg, pp. 80-92 CrossRef
  4. Obdr啪谩lek, J. Clique-width and parity games. In: Duparc, J., Henzinger, T.A. eds. (2007) Computer Science Logic. Springer, Heidelberg, pp. 54-68 CrossRef
  5. Fearnley, J., Schewe, S. Time and parallelizability results for parity games with bounded treewidth. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. eds. (2012) Automata, Languages, and Programming. Springer, Heidelberg, pp. 189-200 CrossRef
  6. Sudborough, I.H. (1978) On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery 25: pp. 405-414 CrossRef
  7. G枚ller, S., Lohrey, M. (2011) Fixpoint logics over hierarchical structures. Theory Comput. Syst. 48: pp. 93-131 CrossRef
  8. Vollmer, H.: Introduction to Circuit Complexity. Texts in Theoretical Computer Science. Springer (1999)
  9. Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: 32nd Annual Symposium on Foundations of Computer Science, pp. 368鈥?77. IEEE Computer Society (1991)
  10. Walukiewicz, I. Monadic second order logic on tree-like structures. In: Puech, C., Reischuk, R. eds. (1996) STACS 96. Springer, Heidelberg, pp. 401-413 CrossRef
  11. Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 143鈥?52 (2010)
  12. Friedmann, O., Lange, M. Solving parity games in practice. In: Liu, Z., Ravn, A.P. eds. (2009) Automated Technology for Verification and Analysis. Springer, Heidelberg, pp. 182-196 CrossRef
  13. Courcelle, B. Graphs as relational structures: An algebraic and logical approach. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. eds. (1991) Graph Grammars and Their Application to Computer Science. Springer, Heidelberg, pp. 238-252 CrossRef
  14. Courcelle, B., Makowsky, J.A., Rotics, U. (2000) Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33: pp. 125-150 CrossRef
  15. Arnborg, S., Corneil, D.G., Proskurowski, A. (1987) Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8: pp. 277-284 CrossRef
  16. Downey, M.R.R.G., Fellows: Parameterized Complexity. Monographs in Computer Science. Springer (1999)
  17. Courcelle, B., Olariu, S. (2000) Upper bounds to the clique width of graphs. Discrete Applied Mathematics 101: pp. 77-114 CrossRef
  18. Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S. (2009) Clique-width is NP-complete. SIAM J. Discrete Math. 23: pp. 909-939 CrossRef
  19. Lohrey, M. On the parallel complexity of tree automata. In: Middeldorp, A. eds. (2001) Rewriting Techniques and Applications. Springer, Heidelberg, pp. 201-215 CrossRef
  20. Gr盲del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. LNCS, vol.聽2500. Springer, Heidelberg (2002)
  21. Seese, D. Tree-partite graphs and the complexity of algorithms. In: Budach, L. eds. (1985) Fundamentals of Computation Theory. Springer, Heidelberg, pp. 412-421 CrossRef
  
• 作者单位：Foundations of Software Science and Computation Structures
• 丛书名：978-3-662-46677-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper it is shown that deciding the winner of a parity game is in LogCFL, if the underlying graph has bounded tree-width, and in LogDCFL, if the tree-width is at most 2. It is also proven that parity games of bounded clique-width can be solved in LogCFL via a log-space reduction to the bounded tree-width case, assuming that a k-expression for the parity game is part of the input.