Publikationen

Noch nicht erschienen

• E. Grädel, Ł. Kaiser, D. Berwanger, and R. Rabinovich. Entanglement and the Complexity Measures for Directed Graphs. Submitted for publication.             
  BibTeX

  @unpublished{BGKR12,
       title = {Entanglement and the Complexity Measures for Directed Graphs},
       author = {Erich Gr{\"a}del and {\L}ukasz Kaiser and Dietmar Berwanger and Roman Rabinovich},
       note = {Submitted for publication},
       url = {http://logic.rwth-aachen.de/~rabinovich/entangle.pdf},
  }
  

2011

• D. Neider, R. Rabinovich, and M. Zimmermann. Solving Muller Games via Safety Games. Technical Report. RWTH Aachen University, 2011.                                 
  Abstract   BibTeX

  We show how to transform a Muller game with n vertices into a safety game with (n!)^3 vertices whose solution allows to determine the winning regions of the Muller game and a winning strategy for one player.

  @techreport{NRZ11,
       author = {Daniel Neider and Roman Rabinovich and Martin Zimmermann},
       title = {Solving Muller Games via Safety Games},
       institution = {RWTH Aachen University},
       year = {2011},
       number = {AIB-2011-14},
       month = {july},
       url = {http://aib.informatik.rwth-aachen.de/2010/2011-14.ps.gz},
       key = {Infinite Games, Muller Games, Safety Games, Antichains, Scores},
  }
  

• B. Puchala and R. Rabinovich. Graph Searching, Parity Games and Imperfect Information. arXiv:1110.5575v1 [cs.GT], 2011.                                 
  Abstract   BibTeX

  We investigate the interrelation between graph searching games and games with imperfect information. As key consequence we obtain that parity games with bounded imperfect information can be solved in PTIME on graphs of bounded DAG-width which generalizes several results for parity games on graphs of bounded complexity. We use a new concept of graph searching where several cops try to catch multiple robbers instead of just a single robber. The main technical result is that the number of cops needed to catch r robbers monotonously is at most r times the DAG-width of the graph. We also explore aspects of this new concept as a refinement of directed path-width which accentuates its connection to the concept of imperfect information.

  @misc{PR11,
       author = {Bernd Puchala and Roman Rabinovich},
       title = {Graph Searching, Parity Games and Imperfect Information},
       howpublished = {arXiv:1110.5575v1 [cs.GT]},
       year = {2011},
       url = {http://logic.rwth-aachen.de/~puchala/multiple-Robbers.pdf},
  }
  

2010

• B. Puchala and R. Rabinovich. Parity Games with Partial Information Played on Graphs of Bounded Complexity. In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science 2010, MFCS '10, vol. 6281 of LNCS, pp. 604–615. Springer, 2010.                                 
  Abstract   BibTeX

  We address the strategy problem for parity games with partial information and observable colors, played on finite graphs of bounded graph complexity. We consider several measures for the complexity of graphs and analyze in which cases, bounding the measure decreases the complexity of the strategy problem on the corresponding classes of graphs. We prove or disprove that the usual powerset construction for eliminating partial information preserves boundedness of the graph complexity. For the case where the partial information is unbounded we prove that the construction does not preserve boundedness of any measure we consider. We also prove that the strategy problem is EXPTIME-hard on graphs with directed path-width at most 2 and PSPACE-complete on acyclic graphs. For games with bounded partial information we obtain that the powerset construction, while neither preserving boundedness of entanglement nor of (undirected) tree-width, does preserve boundedness of directed path-width. Furthermore, if tree-width is bounded then DAG-width of the resulting graph is bounded. Therefore, parity games with bounded partial information, played on graphs with bounded directed path-width or tree-width can be solved in polynomial time.

  @inproceedings{PR10,
       author = {Bernd Puchala and Roman Rabinovich},
       title = {Parity Games with Partial Information Played on Graphs of Bounded Complexity},
       booktitle = {Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science 2010, MFCS~'10},
       publisher = {Springer},
       series = {LNCS},
       volume = {6281},
       year = {2010},
       pages = {604--615},
       url = {http://logic.rwth-aachen.de/~puchala/bounded_partial.pdf},
  }
  

2009

• E. Grädel, Ł. Kaiser, and R. Rabinovich. Directed Graphs of Entanglement Two. In Proceedings of the 17th International Symposium on Fundamentals of Computation Theory, FCT '09, vol. 5699 of LNCS, pp. 169–181. Springer, 2009.                                 
  Abstract   BibTeX

  Entanglement is a complexity measure for directed graphs that was used to show that the variable hierarchy of the propositional modal $\mu$-calculus is strict. While graphs of entanglement zero and one are indeed very simple, some graphs of entanglement two already contain interesting nesting of cycles. This motivates our study of the class of graphs of entanglement two, as these are both simple in a sense and already complex enough for modelling certain structured systems. Undirected graphs of entanglement two were already studied by Belkhir and Santocanale and a structural decomposition for such graphs was given. We study the general case of directed graphs of entanglement two and prove that they can be decomposed as well, in a way similar to the known decompositions for tree-width, DAG-width and Kelly-width. Moreover, we show that all graphs of entanglement two have both DAG-width and Kelly-width three. Since there exist both graphs with DAG-width three and graphs with Kelly-width three, but with arbitrary high entanglement, this confirms that graphs of entanglement two are a very basic class of graphs with cycles intertwined in an interesting way.

  @inproceedings{GKR09,
       author = {Erich Gr{\"a}del and {\L}ukasz Kaiser and Roman Rabinovich},
       title = {Directed Graphs of Entanglement Two},
       booktitle = {Proceedings of the 17th International Symposium on Fundamentals of Computation Theory, FCT~'09},
       publisher = {Springer},
       series = {LNCS},
       volume = {5699},
       year = {2009},
       pages = {169--181},
       url = {http://logic.rwth-aachen.de/~kaiser/entanglement2.pdf},
  }
  

2008

• R. Rabinovich. Complexity Measures of Directed Graphs. Diploma thesis, RWTH-Aachen, 2008.             
  BibTeX

  @misc{Rabinovich08,
       author = {Roman Rabinovich},
       title = {Complexity Measures of Directed Graphs},
       howpublished = {Diploma thesis, RWTH-Aachen},
       year = {2008},
       url = {http://logic.rwth-aachen.de/~rabinovich/diplomarbeit.pdf},
  }