Publications

Łukasz Kaiser

2015

  • E. Grädel, Ł. Kaiser, W. Pakusa, and S. Schalthöfer. Characterising Choiceless Polynomial Time with First-Order Interpretations. In Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 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.             

2013

  • F. Abu Zaid, E. Grädel, Ł. Kaiser, and W. Pakusa. Model-Theoretic Properties of omega-Automatic Structures. Theory of Computing Systems, Special Issue dedicated to STACS 2012, 2013.             

2012

  • F. Abu Zaid, E. Grädel, and Ł. Kaiser. The Field of Reals is not omega-Automatic. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012 (C. Dürr and T. Wilke, Eds.), 2012.                                 
  • D. Berwanger, E. Grädel, Ł. Kaiser, and R. Rabinovich. Entanglement and the Complexity of Directed Graphs. Theoretical Computer Science, vol. 463(0), pp. 2–25, 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.                                 
  • D. Fischer and Ł. Kaiser. Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems. Logical Methods in Computer Science, vol. 8(3), 2012.                                 
  • Ł. 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.             

2011

  • D. Berwanger, Ł. Kaiser, and S. Lessenich. Imperfect Recall and Counter Games. Technical Report. Laboratoire Spécification et Vérification, ENS Cachan, France, 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.                                 
  • V. Bárány, Ł. Kaiser, and A. Rabinovich. Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Chains. J. Symb. Logic, vol. 76(2), pp. 603-619, 2011.                                 
  • D. Fischer and Ł. Kaiser. Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011 (2), vol. 6756 of Lecture Notes in Computer Science, pp. 404–415. Springer, 2011.                                 

2010

  • D. Berwanger and Ł. Kaiser. Information Tracking in Games on Graphs. Journal of Logic, Language and Information, 2010.                                 
  • V. Bárány, Ł. Kaiser, and A. Rabinovich. Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Trees. Fundamenta Informaticae, vol. 100, pp. 1–18, 2010.                                 
  • D. Fischer, E. Grädel, and Ł. Kaiser. Model Checking Games for the Quantitative mu-Calculus. Theory Comput. Syst., vol. 47(3), pp. 696–719, 2010.                                 
  • T. Ganzow and Ł. Kaiser. New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures. In Proceedings of the 19th Annual Conference of the European Association for Computer Science Logic, CSL 2010 (A. Dawar and H. Veith, Eds.), vol. 6247 of Lecture Notes in Computer Science, pp. 366–380. Springer, 2010.                                 
  • M. Holtmann, Ł. Kaiser, and W. Thomas. Degrees of Lookahead in Regular Infinite Games. In Proceedings of the 13th International Conference on Foundations of Software Science and Computation Structures, FOSSACS '10, vol. 6014 of LNCS, pp. 252–266. Springer, 2010.                                 
  • Ł. Kaiser and Ł. Stafiniak. Playing Structure Rewriting Games. In Proceedings of AGI '10. Atlantis Press, 2010.                                 

2009

  • V. Bárány, Ł. Kaiser, and A. Rabinovich. Cardinality quantifiers in MLO over trees. In Proceedings of the 18th EACSL Annual Conference on Computer Science Logic, CSL '09 (E. Grädel and R. Kahle, Eds.), vol. 5771 of LNCS, pp. 117–132. Springer, 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.                                 
  • Ł. Kaiser. Synthesis for Structure Rewriting Systems. In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, MFCS '09, vol. 5734 of LNCS, pp. 415–427. Springer, 2009.                                 

2008

  • D. Fischer, E. Grädel, and Ł. Kaiser. Model Checking Games for the Quantitative μ-Calculus. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 (S. Albers and P. Weil, Eds.), pp. 301–312, 2008.                                 
  • Ł. Kaiser. Logic and Games on Automatic Structures. PhD thesis, RWTH Aachen, 2008.                                 
  • Ł. Kaiser, S. Rubin, and V. Bárány. Cardinality and counting quantifiers on omega-automatic structures. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 (S. Albers and P. Weil, Eds.), pp. 385–396, 2008.                                 

2007

  • E. Grädel and Ł. Kaiser. What kind of memory is needed to win infinitary Muller games? In Interactive Logic (J. van Benthem, B. Löwe, and D. Gabbay, Eds.), vol. 1 of Texts in Logic and Games, pp. 89–116. Amsterdam University Press, 2007.                                 

2006

  • Ł. Kaiser. Game Quantification on Automatic Structures and Hierarchical Model Checking Games. In Proceedings of the 15th Annual Conference on Computer Science Logic, CSL 2006 (Z. Esik, Ed.), vol. 4207 of LNCS, pp. 411–425. Springer, 2006.                                 

2005

  • Ł. Kaiser. Confluence of Right Ground Term Rewriting Systems is Decidable. In FOSSACS 2005, Proceedings of the 8th International Conference on Foundations of Software Science and Computation Structures (V. Sassone, Ed.), vol. 3441 of LNCS, pp. 470–489. Springer, 2005.                                 

2004

  • Ł. Kaiser. Network Design with Selfish Agents. GI Dagstuhl Seminar Report, 2004.