Publications

2015

• F. Canavoi, E. Grädel, S. Lessenich, and W. Pakusa. Defining winning strategies in fixed-point logic. In Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2015.             
  BibTeX

  @inproceedings{CGLP15,
       author = {Felix Canavoi and Erich Gr{\"{a}}del and Simon Lessenich and Wied Pakusa},
       booktitle = {{Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}},
       title = {{Defining winning strategies in fixed-point logic}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/CGLP15.pdf},
       year = {2015},
  }
  

• Ł. Kaiser, M. Lang, S. Lessenich, and C. Löding. A Unified Approach to Boundedness Properties in MSO. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) (S. Kreutzer, Ed.), vol. 41 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 441–456, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.             
  BibTeX

  @inproceedings{KaLaLeLo15,
       author = {{\L}ukasz Kaiser and Martin Lang and Simon Lessenich and Christof L{\"o}ding},
       title = {{A Unified Approach to Boundedness Properties in MSO}},
       booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
       pages = {441--456},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       year = {2015},
       volume = {41},
       editor = {Stephan Kreutzer},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://logic.rwth-aachen.de/pub/lessenich/KaLaLeLo15.pdf},
  }
  

• S. Lessenich. Counting Logics and Games with Counters. PhD thesis, RWTH Aachen University, 2015.             
  BibTeX

  @phdthesis{Lessenich15,
       author = {Simon Lessenich},
       school = {{RWTH} Aachen University},
       title = {Counting Logics and Games with Counters},
       url = {https://publications.rwth-aachen.de/record/466786/files/466786.pdf},
       year = {2015},
  }
  

2012

• D. Berwanger, Ł. Kaiser, and S. Lessenich. Solving Counter Parity Games. In Mathematical Foundations of Computer Science 2012 (B. Rovan, V. Sassone, and P. Widmayer, Eds.), vol. 7464 of Lecture Notes in Computer Science, pp. 160-171. Springer Berlin / Heidelberg, 2012.                                 
  Abstract   BibTeX

  We study a class of parity games equipped with counters that evolve according to arbitrary non-negative affine functions. These games capture several cost models for dynamic systems from the literature. We present an elementary algorithm for computing the exact value of a counter parity game, which both generalizes previous results and improves their complexity. To this end, we introduce a class of omega-regular games with imperfect information and imperfect recall, solve them using automata-based techniques, and prove a correspondence between finite-memory strategies in such games and strategies in counter parity games.

  @incollection{BKL12,
       author = {Dietmar Berwanger and {\L}ukasz Kaiser and Simon Lessenich},
       title = {Solving Counter Parity Games},
       booktitle = {Mathematical Foundations of Computer Science 2012},
       series = {Lecture Notes in Computer Science},
       editor = {Branislav Rovan and Vladimiro Sassone and Peter Widmayer},
       publisher = {Springer Berlin / Heidelberg},
       isbn = {978-3-642-32588-5},
       keyword = {Computer Science},
       pages = {160-171},
       volume = {7464},
       note = {10.1007/978-3-642-32589-2_17},
       year = {2012},
       url = {http://www.logic.rwth-aachen.de/pub/lessenich/counter_parity.pdf},
  }
  

• E. Grädel and S. Lessenich. Banach-Mazur Games with Simple Winning Strategies. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (P. Cégielski and A. Durand, Eds.), vol. 16 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 305–319, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.             
  BibTeX

  @inproceedings{GL12,
       author = {Erich Gr{\"a}del and Simon Lessenich},
       title = {{Banach-Mazur Games with Simple Winning Strategies}},
       booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
       pages = {305--319},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-939897-42-2},
       issn = {1868-8969},
       year = {2012},
       volume = {16},
       editor = {Patrick C{\'e}gielski and Arnaud Durand},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://www.logic.rwth-aachen.de/pub/lessenich/BMGamesSimple.pdf},
       urn = {urn:nbn:de:0030-drops-36806},
       doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2012.305},
       annote = {Keywords: Banach-Mazur games, winning strategies, positional determinacy, Muller winning conditions},
  }
  

• Ł. Kaiser and S. Lessenich. A Counting Logic for Structure Transition Systems. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (P. Cégielski and A. Durand, Eds.), vol. 16 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 366–380, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.             
  BibTeX

  @inproceedings{KL12,
       author = {{\L}ukasz Kaiser and Simon Lessenich},
       title = {{A Counting Logic for Structure Transition Systems}},
       booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
       pages = {366--380},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-939897-42-2},
       issn = {1868-8969},
       year = {2012},
       volume = {16},
       editor = {Patrick C{\'e}gielski and Arnaud Durand},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://www.logic.rwth-aachen.de/pub/lessenich/itrs_qmu.pdf},
       urn = {urn:nbn:de:0030-drops-36848},
       doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2012.366},
       annote = {Keywords: Logic in Computer Science, Quantitative Logics, Model Checking},
  }
  

2011

• D. Berwanger, Ł. Kaiser, and S. Lessenich. Imperfect Recall and Counter Games. Technical Report. Laboratoire Spécification et Vérification, ENS Cachan, France, 2011.             
  BibTeX

  @techreport{BKL11,
       author = {Dietmar Berwanger and {\L}ukasz Kaiser and Simon Lessenich},
       institution = {Laboratoire Sp{\'e}cification et V{\'e}rification, ENS Cachan, France},
       month = {Sep.},
       number = {LSV-11-20},
       title = {{Imperfect Recall and Counter Games}},
       type = {Research Report},
       url = {http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/rr-lsv-2011-20.pdf},
       year = {2011},
  }
  

• S. Lessenich. Banach-Mazur Games with Simple Winning Strategies. Diploma thesis, RWTH Aachen University, 2011.             
  BibTeX

  @misc{Le11,
       author = {Simon Lessenich},
       howpublished = {Diploma thesis, RWTH Aachen University},
       title = {{Banach-Mazur Games with Simple Winning Strategies}},
       url = {http://logic.rwth-aachen.de/~lessenich/diplomarbeit.pdf},
       year = {2011},
  }