Publications

2013

• B. Puchala. Synthesis of Winning Strategies for Interaction under Partial Information. PhD thesis, RWTH Aachen University, 2013.             
  BibTeX

  @phdthesis{Puchala13,
       author = {Bernd Puchala},
       school = {{RWTH} Aachen University},
       title = {Synthesis of Winning Strategies for Interaction under Partial Information},
       url = {http://logic.rwth-aachen.de/~puchala/diss.pdf},
       year = {2013},
  }
  

2011

• D. Berwanger, Ł. Kaiser, and B. Puchala. A Perfect-Information Construction for Coordination in Games. In 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS '11, pp. 387-398. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011.                                 
  Abstract   BibTeX

  We present a general construction for eliminating imperfect information from games with several players who coordinate against nature, and to transform them into two-player games with perfect information while preserving winning strategy profiles. The construction yields an infinite game tree with epistemic models associated to nodes. To obtain a more succinct representation, we define an abstraction based on homomorphic equivalence, which we prove to be sound for games with observable winning conditions. The abstraction generates finite game graphs in several relevant cases, and leads to a new semi-decision procedure for multi-player games with imperfect information.

  @inproceedings{BKP11,
       author = {Dietmar Berwanger and {\L}ukasz Kaiser and Bernd Puchala},
       booktitle = {31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS~'11},
       pages = {387-398},
       publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
       title = {{A Perfect-Information Construction for Coordination in Games}},
       url = {http://logic.rwth-aachen.de/~puchala/tracking.pdf},
       year = {2011},
  }
  

• W. Fridman and B. Puchala. Distributed Synthesis for Regular and Contextfree Specifications. In Proceedings of the 36th International Symosium on Mathematical Foundations of Computer Science, MFCS 2011, Lecture Notes in Computer Science, pp. 532–543. Springer, 2011.                                 
  Abstract   BibTeX

  We adress the controller synthesis problem for distributed systems with regular and deterministic contextfree specifications. Our main result is a complete characterization of the decidable architectures for local specifications. This extends existing results on local specifications in two directions. First, we consider arbitrary, not necessarily acyclic, architectures and second, we allow deterministic contextfree specifications. Moreover, we show that as soon as one considers global deterministic contextfree specifications, even very simple architectures are undecidable.

  @inproceedings{FP11,
       author = {Wladimir Fridman and Bernd Puchala},
       booktitle = {Proceedings of the 36th International Symosium on Mathematical Foundations of Computer Science, MFCS~2011},
       pages = {532--543},
       publisher = {Springer},
       series = {Lecture Notes in Computer Science},
       title = {{Distributed Synthesis for Regular and Contextfree Specifications}},
       url = {http://logic.rwth-aachen.de/~puchala/distributed.pdf},
       year = {2011},
  }
  

• 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},
       howpublished = {arXiv:1110.5575v1 [cs.GT]},
       title = {{Graph Searching, Parity Games and Imperfect Information}},
       url = {http://logic.rwth-aachen.de/~puchala/multiple-Robbers.pdf},
       year = {2011},
  }
  

2010

• B. Puchala. Asynchronous Omega-Regular Games with Partial Information. In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science 2010, MFCS '10, vol. 6281 of LNCS, pp. 592–603. Springer, 2010.                                 
  Abstract   BibTeX

  We address the strategy problem for omega-regular two-player games with partial information, played on finite game graphs. We consider two different kinds of observability on a general model, a standard synchronous and an asynchronous one. In the asynchronous setting, moves which have no visible effect for a player are hidden completely from that player. We generalize the usual powerset construction for eliminating partial information to arbitrary, not necessarily observation based, winning conditions, both in the synchronous and in the asynchronous case, and we show that this generalized construction effectively preserves omega-regular winning conditions. From this we infer decidability of the strategy problem for arbitrary omega-regular winning conditions, in both cases. We also show that our omega-regular framework is sufficient for reasoning about synchronous and asynchronous knowledge by proving that any formula of the epistemic temporal specification formalism ETL can be effectively translated into an S1S-formula defining the same specification.

  @inproceedings{Puchala10,
       author = {Bernd Puchala},
       booktitle = {Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science 2010, MFCS~'10},
       pages = {592--603},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Asynchronous Omega-Regular Games with Partial Information}},
       url = {http://logic.rwth-aachen.de/~puchala/asynchronous.pdf},
       volume = {6281},
       year = {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},
       booktitle = {Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science 2010, MFCS~'10},
       pages = {604--615},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Parity Games with Partial Information Played on Graphs of Bounded Complexity}},
       url = {http://logic.rwth-aachen.de/~puchala/bounded_partial.pdf},
       volume = {6281},
       year = {2010},
  }
  

2008

• B. Puchala. Infinite Two-Player Games with Partial Information: Logic and Algorithms. Diploma thesis, RWTH-Aachen, 2008.             
  BibTeX

  @misc{Puchala08,
       author = {Bernd Puchala},
       howpublished = {Diploma thesis, RWTH-Aachen},
       title = {{Infinite Two-Player Games with Partial Information: Logic and Algorithms}},
       url = {http://logic.rwth-aachen.de/~puchala/dipl.pdf},
       year = {2008},
  }