# Publications

### 2018

• E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity. arXiv:1802.09377 [cs.LO], 2018.

### 2017

• F. Abu Zaid, A. Dawar, E. Grädel, and W. Pakusa. Definability of Summation Problems for Abelian Groups and Semigroups. In Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017.
• F. Abu Zaid, E. Grädel, and F. Reinhardt. Advice Automatic Structures and Uniformly Automatic Classes. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017.
• K. M. Dannert. Succinct Counting and Progress Measures for Solving Infinite Games. Master thesis, RWTH Aachen University, 2017.
• M. Grohe and W. Pakusa. Descriptive Complexity of Linear Equation Systems and Applications to Propositional Proof Complexity. In Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017.
• E. Grädel, B. Pago, and W. Pakusa. The Model-Theoretic Expressiveness of Propositional Proof Systems. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017.
• E. Grädel and V. Tannen. Semiring Provenance for First-Order Model Checking. arXiv:1712.01980 [cs.LO], 2017.

### 2016

• F. Abu Zaid. Algorithmic Solutions via Model Theoretic Interpretations. PhD thesis, RWTH Aachen University, 2016.
• E. Grädel and S. Hegselmann. Counting in Team Semantics. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (J. Talbot and L. Regnier, Eds.), vol. 62 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 35:1–35:18, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.
• E. Grädel. Games for Inclusion Logic and Fixed-Point Logic. In Dependence Logic: Theory and Applications (S. Abramsky et al., Eds.), pp. 73–98. Birkhäuser, 2016.
• W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen University, 2016.
• W. Pakusa, S. Schalthöfer, and E. Selman. Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (J. Talbot and L. Regnier, Eds.), vol. 62 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 19:1–19:17, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.

### 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.
• E. Grädel and M. Grohe. Is Polynomial Time Choiceless? In Fields of Logic and Computation II. Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, vol. 9300 of LNCS, pp. 193-209. Springer, 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.
• E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! CoRR (a conference version appeared in the proceedings of CSL'15), vol. abs/1503.05423, 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.
• S. Lessenich. Counting Logics and Games with Counters. PhD thesis, RWTH Aachen University, 2015.

### 2014

• F. Abu Zaid, E. Grädel, M. Grohe, and W. Pakusa. Choiceless Polynomial Time on structures with small Abelian colour classes. In Mathematical Foundations of Computer Science 2014, vol. 8634 of Lecture Notes in Computer Science, pp. 50-62. Springer, 2014.
• F. Abu Zaid, E. Grädel, and S. Jaax. Bisimulation Safe Fixed Point Logic. Advances in Modal Logic, Volume 10, 2014.
• E. Grädel and M. Otto. The Freedoms of (Guarded) Bisimulation. In Johan van Benthem on Logic and Information Dynamics (A. Baltag and S. Smets, Eds.), vol. 5 of Outstanding Contributions to Logic, pp. 3-31. Springer, 2014.
• F. Canavoi, E. Grädel, and R. Rabinovich. The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs. Theoretical Computer Science, vol. 560, Part 3(0), pp. 235 - 250, 2014.

### 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.
• A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa. Definability of linear equation systems over groups and rings. Logical Methods in Computer Science, Special Issue dedicated to CSL 2012, 2013.
• D. Fischer. The Quantitative mu-Calculus. PhD thesis, RWTH Aachen University, 2013.
• E. Grädel. Model-Checking Games for Logics of Incomplete Information. Theoretical Computer Science, Special Issue dedicated to GandALF 2011, pp. 2–14, 2013.
• E. Grädel and J. Väänänen. Dependence and Independence. Studia Logica, vol. 101(2), pp. 399-410, 2013.
• B. Puchala. Synthesis of Winning Strategies for Interaction under Partial Information. PhD thesis, RWTH Aachen University, 2013.
• R. Rabinovich. Graph Complexity Measures and Monotonicity. PhD thesis, RWTH Aachen University, 2013.
• F. Reinhardt. Automatic Structures with Parameters. Diploma thesis, RWTH-Aachen, 2013.
• S. Schalthöfer. Computing on Abstract Structures with Logical Interpretations. Master thesis, RWTH Aachen University, 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.
• A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa. Definability of linear equation systems over groups and rings. 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. 213–227, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.
• D. Fischer and Ł. Kaiser. Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems. Logical Methods in Computer Science, vol. 8(3), 2012.
• T. Ganzow. Definability and Model Checking: The Role of Orders and Compositionality. PhD thesis, RWTH Aachen University, 2012.
• E. Grädel, F. Canavoi, and R. Rabinovich. The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs. In Proceedings of the Third International Symposium on Games, Automata, Logic, and Formal Verification, GandALF 2012 (M. Faella and A. Murano, Eds.), Electronic Proceedings in Theoretical Computer Science, 2012.
• 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.
• E. Grädel and S. Siebertz. Dynamic Definability. In Proceedings of 15th International Conference on Database Theory, ICDT 2012, 2012.
• E. Grädel and J. Väänänen. Dependence, Independence, and Incomplete Information. In Proceedings of 15th International Conference on Database Theory, ICDT 2012, 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.
• D. Neider, R. Rabinovich, and M. Zimmermann. Down the Borel Hierarchy: Solving Muller Games via Safety Games. In Proceedings of the Third International Symposium on Games, Automata, Logic, and Formal Verification, GandALF 2012 (M. Faella and A. Murano, Eds.), Electronic Proceedings in Theoretical Computer Science, 2012.

### 2011

• F. Abu Zaid. Definability in $\omega$-Automatic Structures. Diploma thesis, RWTH-Aachen, 2011.
• K. Apt and E. Grädel (Eds.). Lectures in Game Theory for Computer Scientists. Cambridge University Press, 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, E. Grädel, and S. Rubin. Automata-Based Presentations of Infinite Structures. In Finite and Algorithmic Model Theory (J. Esparza, C. Michaux, and C. Steinhorn, Eds.), pp. 1–76, 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.
• 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.
• E. Grädel. Back and Forth Between Logics and Games. In Lectures in Game Theory for Computer Scientists, pp. 99–145. Springer, 2011.
• S. Lessenich. Banach-Mazur Games with Simple Winning Strategies. Diploma thesis, RWTH Aachen University, 2011.
• F. Martins Ferreira, C. M. Freire, M. R. Benevides, L. M. Schechter, and A. T. Martins. Hybrid Logics and NP Graph Properties. In Logic, Language, Information and Computation — 18th International Workshop, WoLLIC 2011, Philadelphia, PA, USA. Proceedings (L. D. Beklemishev and R. de Queiroz, Eds.), vol. 6642 of Lecture Notes in Computer Science, pp. 123–134. Springer Berlin / Heidelberg, 2011.
• F. Martins Ferreira and A. T. Martins. Expressiveness and Definability in Circumscription. Manuscrito, vol. 34(1), pp. 195–227, 2011.
• F. Martins Ferreira and A. T. Martins. Expressible preferential logics. Journal of Logic and Computation (Online), 2011.
• F. Martins Ferreira and A. T. Martins. Recursive Definitions and Fixed-Points on Well-Founded Structures. Theoretical Computer Science, vol. 412(37), pp. 4893–4904, 2011.
• D. Neider, R. Rabinovich, and M. Zimmermann. Solving Muller Games via Safety Games. Technical Report. RWTH Aachen University, 2011.
• B. Puchala and R. Rabinovich. Graph Searching, Parity Games and Imperfect Information. arXiv:1110.5575v1 [cs.GT], 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.
• A. Dawar and E. Grädel. Properties of Almost All Graphs and Generalized Quantifiers. Fundamenta Informaticae, vol. 98, pp. 351–372, 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.
• J. Olschewski and M. Ummels. The Complexity of Finding Reset Words in Finite Automata. In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, vol. 6281 of LNCS, pp. 568–579. Springer, 2010.
• W. Pakusa. Finite Model Theory with Operators from Linear Algebra. Staatsexamensarbeit, RWTH-Aachen University, 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.
• 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.
• M. Ummels. Stochastic Multiplayer Games: Theory and Algorithms. PhD thesis, RWTH Aachen University, 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 and R. Kahle (Eds.). Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic, CSL '09. 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.
• W. Thomas, K. Bollue, D. Gueckel, G. Quiros, M. Slaats, and M. Ummels. DFG Research Training Group “Algorithmic Synthesis of Reactive and Discrete-Continuous Systems (AlgoSyn)”. it – Information Technology, vol. 51(4), 2009.
• M. Ummels and D. Wojtczak. Decision Problems for Nash Equilibria in Stochastic Games. In Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic, CSL '09 (E. Grädel and R. Kahle, Eds.), vol. 5771 of LNCS, pp. 515–530. Springer, 2009.
• M. Ummels and D. Wojtczak. The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 (S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, and W. Thomas, Eds.), vol. 5556 of LNCS, pp. 297–308. Springer, 2009.

### 2008

• D. Berwanger, K. Chatterjee, L. Doyen, T. A. Henzinger, and S. Raje. Strategy Construction for Parity Games with Imperfect Information. In Proceedings of the 19th International Conference on Concurrency Theory, CONCUR 2008, vol. 5201 of LNCS, pp. 325–339. Springer, 2008.
• V. Bárány. A Hierarchy of Automatic $\omega$-Words having a Decidable MSO Theory. RAIRO - Theor. Inf. Appl., vol. 42, pp. 417–450, 2008.
• A. Dawar and E. Grädel. The Descriptive Complexity of Parity Games. In Proceedings of the 17th Annual Conference on Computer Science Logic, CSL 2008, vol. 5213 of LNCS, pp. 354–368. Springer, 2008.
• A. Dermaku, T. Ganzow, G. Gottlob, B. J. McMahan, N. Musliu, and M. Samer. Heuristic Methods for Hypertree Decomposition. In Proceedings of the 7th Mexican International Conference on Artificial Intelligence, MICAI 2008, pp. 1–11, 2008.
• D. Fischer, E. Grädel, and Ł. Kaiser. Model Checking Games for the Quantitative $\mu$-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.
• T. Ganzow and S. Rubin. Order-Invariant {MSO is Stronger than Counting MSO in the Finite}. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 (S. Albers and P. Weil, Eds.), pp. 313–324, 2008.
• E. Grädel. {Banach-Mazur Games on Graphs}. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008 (R. Hariharan, M. Mukund, and V. Vinay, Eds.), Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, 2008.
• E. Grädel and M. Ummels. Solution Concepts and Algorithms for Infinite Multiplayer Games. In New Perspectives on Games and Interaction (K. Apt and R. van Rooij, Eds.), vol. 4 of Texts in Logic and Games, pp. 151–178. Amsterdam University Press, 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.
• B. Puchala. Infinite Two-Player Games with Partial Information: Logic and Algorithms. Diploma thesis, RWTH-Aachen, 2008.
• R. Rabinovich. Complexity Measures of Directed Graphs. Diploma thesis, RWTH-Aachen, 2008.
• M. Ummels. The Complexity of Nash Equilibria in Infinite Multiplayer Games. In Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2008 (R. Amadio, Ed.), vol. 4962 of LNCS, pp. 20–34. Springer, 2008.

### 2007

• D. Berwanger, E. Grädel, and G. Lenzi. The variable hierarchy of the $\mu$-calculus is strict. Theory of Computing Systems, vol. 40, pp. 437–466, 2007.
• D. Berwanger. Admissibility in infinite games. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007 (W. Thomas and P. Weil, Eds.), vol. 4393 of LNCS, pp. 188–199. Springer, 2007.
• V. Bárány. Automatic Presentations of Infinite Structures. PhD thesis, RWTH Aachen, 2007.
• J. Flum, E. Grädel, and T. Wilke (Eds.). Logic and Automata: History and Perspectives. Amsterdam University Press, 2007.
• E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer, 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.
• E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S.Weinstein. Finite Model Theory and Its Applications. Springer, 2007.
• F. Martins Ferreira. Modelos Minimais e Hierarquia de Expressividade. Master thesis, Universidade Federal do Ceará, 2007.
• F. Martins Ferreira and A. T. Martins. On Minimal Models. Logic Journal of the IGPL, vol. 15(5–6), pp. 503–526, 2007.

### 2006

• D. Berwanger, A. Dawar, P. Hunter, and S. Kreutzer. DAG-width and parity games. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006, vol. 3884 of LNCS, pp. 524–536. Springer, 2006.
• D. Berwanger and D. Janin. Automata on Directed Graphs: Vertex versus Edge Marking. In Proceedings of the 3rd International Conference on Graph Transformation, ICGT 2006, vol. 4178 of LNCS, pp. 46–60. Springer, 2006.
• V. Bárány. A Hierarchy of Automatic Words having a Decidable MSO Theory. In Online Proceedings of the 11th Journ{ées Montoises, Rennes} (D. Caucal, Ed.), 2006.
• V. Bárány, C. Löding, and O. Serre. Regularity Problems for Visibly Pushdown Languages. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006 (B. Durand and W. Thomas, Eds.), vol. 3884 of LNCS, pp. 420–431. Springer, 2006.
• V. Bárány. Invariants of Automatic Presentations and Semi-Synchronous Transductions. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006 (B. Durand and W. Thomas, Eds.), vol. 3884 of LNCS, pp. 289–300. Springer, 2006.
• A. Dawar, E. Grädel, and S. Kreutzer. Backtracking Games and Inflationary Fixed Points. Theoretical Computer Science, vol. 350, pp. 174–187, 2006.
• E. Grädel and I. Walukiewicz. Positional Determinacy of Games with Infinitely Many Priorities. Logical Methods in Computer Science, 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.
• F. Martins Ferreira and A. T. Martins. The Predicate-Minimizing Logic MIN. In Advances in Artificial Intelligence - IBERAMIA-SBIA 2006 (J. Sichman, H. Coelho, and S. Rezende, Eds.), vol. 4140 of Lecture Notes in Computer Science, pp. 582–591. Springer Berlin / Heidelberg, 2006.
• M. Ummels. Rational Behaviour and Strategy Construction in Infinite Multiplayer Games. In Proceedings of the 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006 (S. Arun-Kumar and N. Garg, Eds.), vol. 4337 of LNCS, pp. 212–223. Springer, 2006.

### 2005

• D. Berwanger. Games and Logical Expressiveness. PhD thesis, RWTH Aachen, 2005.
• D. Berwanger and E. Grädel. Entanglement – {A Measure for the Complexity of Directed Graphs with Applications to Logic and Games}. In Proceedings of LPAR 2004, Montevideo, Uruguay, vol. 3452 of LNCS, pp. 209–223. Springer, 2005.
• D. Berwanger and G. Lenzi. The variable hierarchy of the $\mu$-calculus is strict. In STACS 2005, Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, vol. 3404 of LNCS, pp. 97–109. Springer, 2005.
• A. Blumensath and S. Kreutzer. An Extension to {Muchnik's Theorem}. Journal of Logic and Computation, vol. 15, pp. 59–74, 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.
• M. Ummels. Rational Behaviour and Strategy Construction in Infinite Multiplayer Games. Diploma thesis, RWTH Aachen, 2005.

### 2004

• D. Berwanger and E. Grädel. Fixed-Point Logics and Solitaire Games. Theory of Computing Systems, vol. 37, pp. 675–694, 2004.
• A. Blumensath and E. Grädel. Finite Presentations of Infinite Structures: Automata and Interpretations. Theory of Computing Systems, vol. 37, pp. 641 – 674, 2004.
• A. Dawar, E. Grädel, and S. Kreutzer. Inflationary fixed points in modal logic. ACM Transations on Computational Logic, vol. 5, pp. 282 – 315, 2004.
• A. Dawar, S. Kreutzer, and E. Grädel. Backtracking Games and Inflationary Fixed Points. In Proc. 31st International Colloquium on Automata, Languages and Programming – ICALP'04. Springer, 2004.
• E. Grädel. Positional Determinacy of Infinite Games. In Proceedings of STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science, vol. 2996 of LNCS, pp. 2 – 18. Springer, 2004.
• Ł. Kaiser. Network Design with Selfish Agents. GI Dagstuhl Seminar Report, 2004.
• A. Nowack. Slicing Abstract State Machines. In Abstract State Machines – Advances in Theory and Practice, vol. 3052 of LNCS. Springer, 2004.
• A. Nowack. A Guarded Fragment for Abstract State Machines. In Proceedings of the ESSLLI 2004 Workshop on Guarded Fragments, 2004.

### 2003

• D. Berwanger. Game Logic is Strong Enough for Parity Games. Studia Logica, vol. 75(2), pp. 205–219, 2003.
• D. Berwanger, E. Grädel, and S. Kreutzer. Once Upon a Time in the West. {Determinacy, Complexity and Definability of Path Games.}. In Proceedings of the 10th International Conference on Logic for Programming and Automated Reasoning, vol. 2850 of LNCS, pp. 226–240. Springer, 2003.
• A. Blumensath. Structures of Bounded Partition Width. PhD thesis, RWTH Aachen, 2003.
• E. Grädel. Decidable fragments of first-order and fixed-point logic. {From prefix-vocabulary classes to guarded logics.}. In Proceedings of Kalm{ár Workshop on Logic and Computer Science, Szeged}, 2003.
• E. Grädel and S. Kreutzer. Will Deflation Lead to Depletion? {On Non-Monotone Fixed Point Inductions.}. In Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS), pp. 158 – 167, 2003.
• E. Grädel and A. Nowack. Quantum Computing and Abstract State Machines. In Abstract State Machines – Advances in Theory and Applications, vol. 2589 of LNCS, pp. 309 – 323. Springer, 2003.
• S. Kreutzer. Pure and Applied Fixed-Point Logics. In Ausgezeichnete {Informatikdissertationen 2002} (D. Wagner et al., Eds.), vol. D-3 of Lecture Notes in Informatics – Dissertations, pp. 59–68. German Informatics Society, 2003.
• A. Nowack. Deciding the Verification Problem for Abstract State Machines. In Abstract State Machines – Advances in Theory and Applications, vol. 2589 of LNCS. Springer, 2003.

### 2002

• A. Blumensath. Axiomatising Tree-interpretable Structures. In Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science, vol. 2285 of LNCS, pp. 596–607. Springer, 2002.
• A. Blumensath and E. Grädel. Finite Presentations of Infinite Structures. In Proceedings of the 2nd International Workshop on Complexity in Automated Deduction, CiAD 2002, 2002.
• A. Dawar and S. Kreutzer. Generalising Automaticity to Modal Properties of Finite Structures. In Foundations of Software Technology and Theoretical Computer Science, 2002.
• Dietmar Berwanger and Achim Blumensath. The Monadic Theory of Tree-like Structures. In Automata, Logics, and Infinite Games (Erich Grädel, W. Thomas, and T. Wilke, Eds.), LNCS, pp. 285–301. Springer Verlag, 2002.
• Dietmar Berwanger and Achim Blumensath. Automata for Guarded Fixed Point Logics. In Automata, Logics, and Infinite Games (Erich Grädel, Wolfgang Thomas, and Thomas Wilke, Eds.), LNCS, pp. 343–355. Springer Verlag, 2002.
• Dietmar Berwanger and Erich Grädel. Fixed point formulae and solitaire games. In Proceedings of the 2nd International Workshop on Complexity in Automated Deduction, CiAD 2002, 2002.
• Dietmar Berwanger, Erich Grädel, and Giacomo Lenzi. On the variable hierarchy of the modal mu-calculus. In Computer Science Logic, CSL 2002 (J. Bradfield, Ed.), vol. 2471 of LNCS, pp. 352–366. Springer, 2002.
• Eric Rosen. Some aspects of model theory and finite structures. Bulletin of Symbolic Logic, vol. 8(3), pp. 380 – 403, 2002.
• G. Gottlob, E. Grädel, and H. Veith. Datalog {LITE: A deductive query language with linear time model checking}. ACM Transactions on Computational Logic, vol. 3(1), pp. 1–35, 2002.
• E. Grädel. Guarded fixed point logic and the monadic theory of trees. Theoretical Computer Science, vol. 288, pp. 129–152, 2002.
• E. Grädel. Model Checking Games. In Proceedings of WOLLIC 02, vol. 67 of Electronic Notes in Theoretical Computer Science. Elsevier, 2002.
• E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. ACM Transactions on Computational Logics, vol. 3(3), pp. 418 – 463, 2002.
• E. Grädel, W. Thomas, and T. Wilke (Eds.). Automata, Logics, and Infinite Games. Springer, 2002.
• C. Hirsch. Guarded Logics: Algorithms and Bisimulation. PhD thesis, RWTH Aachen, 2002.
• S. Kreutzer. Expressive Equivalence of Least and Inflationary Fixed-Point Logic. In Proceedings of the 17th IEEE Symp. on Logic in Computer Science (LICS), 2002.
• S. Kreutzer. Partial Fixed-Point Logic on Infinite Structures. In Annual Conference of the European Association for Computer Science Logic (CSL), vol. 2471 of Lecture Notes in Computer Science (LNCS). Springer, 2002.
• S. Kreutzer. Pure and Applied Fixed-Point Logics. PhD thesis, RWTH Aachen, 2002.

### 2001

• D. Berwanger and E. Grädel. Games and Model Checking for Guarded Logics. In Proceedings of the 8th International Conference on Logic for Programming and Automated Reasoning, {LPAR 2001, Havana} (R. Nieuwenhuis and A. Voronkov, Eds.), vol. 2250 of LNCS. Springer, 2001.
• D. Berwanger. Game Logic is Strong Enough for Parity Games. In Proceedings of the ESSLLI 2001 Workshop on Logic and Games (M. Pauly and G. Sandu, Eds.), Helsinki, 2001.
• A. Blumensath. Prefix-Recognisable Graphs and Monadic Second-Order Logic. Technical Report. RWTH Aachen, 2001.
• A. Dawar, E. Grädel, and S. Kreutzer. Inflationary Fixed Points in Modal Logic. In Proceedings of 15th Annual Conference of the European Association for Computer Science Logic CSL 2001, LNCS. Springer, 2001.
• J. Duparc. Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. Journal of Symbolic Logic, vol. 66(1), pp. 56–86, 2001.
• J. Duparc. Wadge hierarchy and Veblen hierarchy. Part II: Borel sets of infinite rank. Submitted to Journal of Symbolic Logic, 2001.
• J. Duparc. The Steel Hierarchy of Ordinal Valued Borel Mappings. Submitted to Journal of Symbolic Logic, 2001.
• J. Duparc. A coarsification of the Wagner Hierarchy. Submitted to Theoretical Computer Science, 2001.
• O. Finkel, J. Duparc, and J. Ressayre. Computer Science and the fine structure of Borel sets. Theoretical Computer Science, pp. 85–105, 2001.
• E. Grädel. Why are modal logics so robustly decidable?. In Current Trends in Theoretical Computer Science. Entering the 21st Century (G. Paun, G. Rozenberg, and A. Salomaa, Eds.), pp. 393–408. World Scientific, 2001.
• C. Hirsch and R. Fleischer. Graph Drawings and Its Applications. In Drawing Graphs – Methods and Models (M. Kaufmann and D. Wagner, Eds.), LNCS, pp. 1–22. Springer, 2001.
• S. Kreutzer. Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls. In Proceedings of the 8th International Conference on Database Theory (ICDT), vol. 1973 of LNCS, pp. 248–262. Springer, 2001.
• S. Kreutzer. Operational Semantics for Fixed-Point Logics on Constraint Databases. In Proceedings of the 8th International Conference on Logic for Programming and Automated Reasoning, {LPAR 2001, Havana}, vol. 2250 of LNCS, pp. 465–479. Springer, 2001.

### 2000

• D. Berwanger. Games and Model Checking for Guarded Logics. Diploma thesis, RWTH-Aachen, 2000.
• A. Blumensath. Bounded Arithmetic and Descriptive Complexity. In Proceedings of 14th Annual Conference of the European Association for Computer Science Logic CSL 2000, vol. 1862 of LNCS, pp. 232–246. Springer, 2000.
• A. Blumensath and E. Grädel. Automatic Structures. In Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, pp. 51–62, 2000.
• J. Duparc. Anti-chains of mappings from $\omega^\omega$ on some BQO. 2000.
• E. Gonçalvès and E. Grädel. Decidability issues for action guarded logics. In Proceedings of 2000 International Workshop on Description Logics – DL2000, pp. 123–132, 2000.
• G. Gottlob, E. Grädel, and H. Veith. Linear Time Datalog for Branching Time Logic. In Logic-Based Artificial Intelligence (J. Minker, Ed.). Kluwer, 2000.
• E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. In Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, pp. 217–228, Santa Barbara, 2000.
• C. Hirsch and S. Tobies. A Tableau Algorithm for the Clique Guarded Fragment. In Proceedings of the Workshop Advances in Modal Logic {AiML 2000}, Leipzig, Germany, 2000.
• S. Kreutzer. Fixed-point Query Languages for Linear Constraint Databases. In Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS), 2000, pp. 116–125. ACM press, 2000.
• A. Nowack. Complexity Theory via Abstract State Machines. Diploma thesis, RWTH-Aachen, 2000.
• E. Rosen and J. Tyszkiewicz. {SO$(\forall\exists^*)$ sentences and their asymptotic probabilities}. Mathematical Logic Quarterly, vol. 46, pp. 435–52, 2000.
• M. Spielmann. Model Checking Abstract State Machines and Beyond. In International Workshop on Abstract State Machines ASM 2000, LNCS, pp. 323–340. Springer, 2000.
• M. Spielmann. Verification of Relational Transducers for Electronic Commerce. In 19th ACM Symposium on Principles of Database Systems PODS 2000, Dallas, pp. 92–93. ACM Press, 2000.

### 1999

• A. Blumensath. Automatic Structures. Diploma thesis, RWTH-Aachen, 1999.
• J. Duparc. The normal form of Borel sets. Part II : Borel sets of infinite rank. Comptes Rendus de l'Académie des Sciences, pp. 735–740, 1999.
• E. Grädel. Why are modal logics so robustly decidable? Bulletin of the European Association for Theoretical Computer Science, vol. 68, pp. 90–103, 1999.
• E. Grädel. Decision procedures for guarded logics. In Automated Deduction – CADE16. Proceedings of 16th International Conference on Automated Deduction, Trento, 1999, vol. 1632 of LNCS. Springer, 1999.
• E. Grädel. On the restraining power of guards. Journal of Symbolic Logic, vol. 64, pp. 1719–1742, 1999.
• E. Grädel and S. Kreutzer. Descriptive Complexity Theory for Constraint Databases. In Proceedings of the Annual Conference of the European Association for Computer Science Logic, CSL 99, Madrid, vol. 1683 of LNCS, pp. 67–81. Springer, 1999.
• E. Grädel and A. Malmström. 0-1 Laws for Recursive Structures. Archive for Mathematical Logic, vol. 38, pp. 205–215, 1999.
• E. Grädel. The decidability of guarded fixed point logic. In JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday (J. Gerbrandy, M. Marx, M. de Rijke, and Y. Venema, Eds.). Amsterdam University Press, 1999.
• E. Grädel and M. Otto. On Logics with Two Variables. Theoretical Computer Science, vol. 224, pp. 73–113, 1999.
• E. Grädel, M. Otto, and E. Rosen. Undecidability Results on Two-Variable Logics. Archive for Mathematical Logic, vol. 38, pp. 213–354, 1999.
• E. Grädel and E. Rosen. Preservation theorems for two-variable logic. Mathematical Logic Quarterly, vol. 45, pp. 315–325, 1999.
• E. Grädel and E. Rosen. Two-variable descriptions of regularity. In Proceedings of 14th IEEE Symposium on Logic in Computer Science LICS 99, Trento, pp. 14–23, 1999.
• E. Grädel and M. Spielmann. Logspace Reducibility via Abstract State Machines. In World Congress on Formal Methods (FM 99) (J. Wing, J. Woodcock, and J. Davies, Eds.), vol. 1709 of LNCS, pp. 1738–1757. Springer, 1999.
• E. Grädel and I. Walukiewicz. Guarded Fixed Point Logic. In Proceedings of 14th IEEE Symposium on Logic in Computer Science LICS 99, Trento, pp. 45–54, 1999.
• E. Hoogland, M. Marx, and M. Otto. Beth Definability for the Guarded Fragment. In Proceedings of LPAR'99, LNAI. Springer, 1999.
• S. Kreutzer. Descriptive Complexity Theory for Constraint Databases. Diploma thesis, RWTH-Aachen, 1999.
• F. Neven, M. Otto, J. Tyszkiewicz, and V. den Bussche. Adding FOR-Loops to First-Order Logic. In Proceedings of ICDT'99, vol. 1540 of LNCS, pp. 58–69. Springer, 1999.
• M. Otto. Bounded-Variable Logics: Two, Three, and More. Archive for Mathematical Logic, vol. 38, pp. 235–256, 1999.
• M. Otto. Bisimulation-Invariant Ptime and Higher-Dimensional mu-Calculus. Theoretical Computer Science, vol. 224, pp. 237–265, 1999.
• M. Otto. Eliminating Recursion in the $\mu$-Calculus. In Proceedings of STACS'99, vol. 1563 of LNCS, pp. 531–540. Springer, 1999.
• E. Rosen. An existential fragment of second order logic. Archive for Mathematical Logic, vol. 38, pp. 217–234, 1999.
• M. Spielmann. Automatic Verification of Abstract State Machines. In Proceedings of 11th International Conference on Computer-Aided Verification (CAV 99), vol. 1633 of LNCS, pp. 431–442. Springer, 1999.

### 1998

• E. Grädel. Guarded fragments of first-order logic: a perspective for new description logics? In Proceedings of 1998 International Workshop on Description Logics DL {98}, Trento. CEUR Electronic Workshop Proceedings, 1998.
• E. Grädel and Y. Gurevich. Metafinite Model Theory. Information and Computation, vol. 140, pp. 26–81, 1998.
• E. Grädel, Y. Gurevich, and C. Hirsch. The complexity of query reliability. In 17th ACM Symposium on Principles of Database Systems PODS 98, Seattle. ACM Press, 1998.
• C. Hirsch. The Reliability of Database Queries. Diploma thesis, RWTH-Aachen, 1998.
• P. Kolaitis and M. Otto. {On the Boundedness Problem for Two-Variable First-Order Logic}. In Proceedings of IEEE Symposium on Logic in Computer Science LICS 98, 1998.
• M. Otto. Two-Variable First-Order Logic over Ordered Domains. 1998.
• M. Otto. An interpolation theorem. 1998.
• E. Rosen. On the first-order prefix hierarchy. 1998.
• J. Tyszkiewicz. On the Kolmogorov Expressive Power of Boolean Query Languages. Theoretical Computer Science, vol. 190, pp. 317–361, 1998.

### 1997

• E. Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Springer, 1997.
• E. Grädel, P. Kolaitis, and M. Vardi. On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic, vol. 3, pp. 53–69, 1997.
• E. Grädel, M. Otto, and E. Rosen. Two-Variable Logic with Counting is Decidable. In Proceedings of 12th IEEE Symposium on Logic in Computer Science LICS 97, Warschau, 1997.
• E. Grädel, M. Otto, and E. Rosen. Undecidability Results on Two-Variable Logics. In Proceedings of 14th Symposium on Theoretical Aspects of Computer Science STACS97, vol. 1200 of Lecture Notes in Computer Science, pp. 249–260, 1997.
• Y. Gurevich and M. Spielmann. Recursive Abstract State Machines. JUCS, vol. 3(4), pp. 233–246, 1997.
• A. Malmström. Logic and Approximation. PhD thesis, RWTH Aachen, 1997.
• A. Malmström. Optimization problems with approximation schemes. In Annual Conference of the European Association for Computer Science Logic CSL'96, Selected Papers, Utrecht (NL) (D. van Dalen and M. Bezem, Eds.), vol. 1258 of LNCS, pp. 316–333. Springer, 1997.
• M. Otto. {Canonization for Two Variables and Puzzles on the Square}. Annals of Pure and Applied Logic, vol. 85, pp. 243–282, 1997.
• M. Otto. Capturing Bisimulation-Invariant Ptime. In Proceedings of 4th Symposium on Logical Foundations of Computer Science, LFCS 97, vol. 1234 of LNCS, pp. 294–305. Springer, 1997.
• M. Otto. Bounded variable logics and counting — A study in finite models. Springer, 1997.
• M. Otto. The Logic of Explicitly Representation-Invariant Circuits. Selected Papers of CSL 96, vol. 1258, pp. 369–384, 1997.
• P. Idziak and J. Tyszkiewicz. Monadic Second Order Probabilities in Algebra. Directly Representable Varieties and Groups. In Logic and Random Structures, AMS (R. B. Boppana and J. F. Lynch, Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 79–108, 1997.
• E. Rosen. Modal logic over finite structures. Journal of Logic, Language and Information, vol. 6, pp. 427–439, 1997.
• J. Tyszkiewicz. The Kolmogorov Expression Complexity of Logics. Information and Computation, vol. 135, pp. 113–135, 1997.
• J. Tyszkiewicz. A Note on the Kolmogorov Data Complexity and Nonuniform Logical Definitions. Information Processing Letters, vol. 64, pp. 187–195, 1997.
• J. Tyszkiewicz. Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines. Fundamenta Informaticae, vol. 32, pp. 91–105, 1997.
• J. Tyszkiewicz. Fine Hierarchies of Generic Computation. In Proceedings of International Conference in Database Theory ICDT 97 (F. Afrati and P. Kolaitis, Eds.), vol. 1186 of LNCS, pp. 125–139. Springer, 1997.

### 1996

• K. Compton and E. Grädel. Logical Definability of Counting Functions. Journal of Computer and System Sciences, vol. 53, pp. 283–297, 1996.
• E. Grädel and K. Meer. Descriptive Complexity Theory over the Real Numbers. Mathematics of Numerical Analysis: Real Number Algorithms, vol. 32, pp. 381–403, 1996.
• E. Grädel and G. McColm. Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. Annals of Pure and Applied Logic, vol. 77, pp. 166–199, 1996.
• M. Otto. The {Expressive Power of Fixed-Point Logic with Counting}. Journal of Symbolic Logic, vol. 61, pp. 147–176, 1996.
• M. Otto and J. V. den Bussche. First-{Order Queries on Databases Embedded in an Infinite Structure}. Information Processing Letters, vol. 60, pp. 37–41, 1996.

### 1995

• A. Dawar and E. Grädel. Generalized Quantifiers and 0-1 Laws. In Proceedings of 10th IEEE Symposium on Logic in Computer Science LICS 95, San Diego, pp. 54–64, 1995.
• J. Duparc. The normal form of Borel sets. Part I: Borel sets of finite rank. Comptes Rendus de l'Académie des Sciences, pp. 651–656, 1995.
• J. Duparc. La forme normale des Bor{éliens de rangs finis}. PhD thesis, Université Paris VII, 1995.
• E. Grädel and Y. Gurevich. Tailoring Recursion for Complexity. Journal of Symbolic Logic, vol. 60, pp. 952–969, 1995.
• E. Grädel and Y. Gurevich. Metafinite Model Theory. In Logic and Computational Complexity, Selected Papers (D. Leivant, Ed.), pp. 213–366. Springer, 1995.
• E. Grädel and K. Meer. Descriptive Complexity Theory over the Real Numbers. In Proceedings of the 27th ACM-Symposium on Theory of Computing, STOC 95, Las Vegas, 1995.
• E. Grädel and G. McColm. On the {Power of Deterministic Transitive Closures}. Information and Computation, vol. 119, pp. 129–135, 1995.
• A. Malmström. Log-approximable minimization problems on random input. In Annual Conference of the European Association for Computer Science Logic CSL'94, Selected Papers, Kazimierz (Poland), vol. 933 of LNCS, pp. 217–227. Springer, 1995.
• M. Otto. Bounded variable logics and counting — A study in finite models. 1995.
• M. Otto. A note on the number of monadic quantifiers in monadic {$\Sigma^1\_1$}. Information Processing Letters, vol. 53(6), pp. 337–339, 1995.
• M. Otto. Ptime canonization for two variables with counting. In Proceedings of 10th IEEE Symposium on Logic in Computer Science LICS 95, pp. 342–352, 1995.
• J. Tyszkiewicz. Probabilities in First-Order Logic of a Unary Function and a Binary Relation. Random Structures and Algorithms, vol. 6, pp. 181–191, 1995.

### 1994

• K. Compton and E. Grädel. Logical Definability of Counting Functions. In Proceedings of 9th IEEE Conference on Structure in Complexity Theory, pp. 255–266, Amsterdam, 1994.
• J. Duparc. A normal form for Borel sets. 1994.
• E. Grädel. Definability on Finite Structures and the Existence of One-Way Functions. Methods of Logic in Computer Science, vol. 1, pp. 299–314, 1994.
• E. Grädel and Y. Gurevich. Tailoring Recursion for Complexity. In Proceedings of 21st International Colloquium on Automata, Languages and Programming ICALP 94, vol. 820 of LNCS, pp. 118–129. Springer, 1994.
• E. Grädel and A. Malmström. Approximable minimization problems and optimal solutions on random input. In Computer Science Logic, 7th Workshop, CSL 93, Swansea 1993, Selected Papers (E. Börger, Y. Gurevich, and K. Meinke, Eds.), vol. 832 of LNCS, pp. 139–149. Springer, 1994.
• M. Otto. Generalized quantifiers for simple properties. In Proceedings of 9th IEEE Symposium on Logic in Computer Science LICS 94, pp. 30–39, 1994.
• J. Tyszkiewicz. Infinitary queries and their asymptotic probabilities II: properties definable in least fixed point logic. Random Structures and Algorithms, vol. 5, pp. 215–234, 1994.

### 1993

• T. Behrendt, K. Compton, and E. Grädel. Optimization Problems: Expressibility, Approximation Properties, and Expected Asymptotic Growth of Optimal Solutions. In Computer Science Logic, 6th Workshop, CSL 92, San Miniato 1992, Selected Papers (E. Börger, G. Jäger, H. K. Büning, S. Martini, and M. M. Richter, Eds.), vol. 702 of LNCS, pp. 43–60. Springer, 1993.
• E. Grädel and M. Otto. Inductive Definability with Counting on Finite Structures. In Computer Science Logic, 6th Workshop, CSL 92, San Miniato 1992, Selected Papers (E. Börger, G. Jäger, H. K. Büning, S. Martini, and M. M. Richter, Eds.), vol. 702 of LNCS, pp. 231–247. Springer, 1993.
• J. Tyszkiewicz. On Asymptotic Probabilities in Logics That Capture DSPACE($łog n$) in Presence of Ordering. In Proceedings of TAPSOFT 93, vol. 668 of LNCS, pp. 569–583. Springer, 1993.
• J. Tyszkiewicz. On Asymptotic Probabilities of Monadic Second Order Properties. In Computer Science Logic, 6th Workshop, CSL 92, San Miniato 1992, Selected Papers (E. Börger, G. Jäger, H. K. Büning, S. Martini, and M. M. Richter, Eds.), vol. 702 of LNCS, pp. 425–439. Springer, 1993.

### 1992

• E. Grädel. Capturing Complexity Classes by Fragments of Second Order Logic. Theoretical Computer Science, vol. 101, pp. 35–57, 1992.
• E. Grädel. On Transitive Closure Logic. In Proceedings of 5th Workshop on Computer Science Logic CSL 91, Bern 1991, vol. 626 of LNCS, pp. 149–163. Springer, 1992.
• E. Grädel and G. McColm. Deterministic versus Nondeterministic Transitive Closure Logic. In Proceedings of 7th IEEE Symposium on Logic in Computer Science LICS 92, pp. 58–63, Santa Cruz, 1992.
• E. Grädel and G. McColm. Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. In Proceedings of 33rd Annual IEEE Symposium on Foundations of Computer Science FOCS 92, pp. 167–176, Pittsburgh, 1992.
• M. Otto. Automorphism Properties of Stationary Logic. Journal of Symbolic Logic, vol. 57, pp. 231–237, 1992.
• M. Otto. EM Functors for a Class of Generalized Quantifiers. Archive for Mathematical Logic, vol. 31, pp. 355–371, 1992.

### 1991

• E. Grädel. Simple Sentences that are Hard to Decide. Information and Computation, vol. 94, pp. 62–82, 1991.
• E. Grädel. The Expressive Power of Second Order Horn Logic. In Proceedings of 8th Symposium on Theoretical Aspects of Computer Science STACS 91, Hamburg 1991, vol. 480 of LNCS, pp. 466–477. Springer, 1991.
• E. Grädel. Capturing Complexity Classes by Fragments of Second Order Logic. In Proceedings of 6th IEEE Conference on Structure in Complexity Theory, pp. 341–352, 1991.
• J. Tyszkiewicz. Infinitary Queries and Their Asymptotic Probabilities I: Properties Definable in Transitive Closure Logic. In Proceedings of Workshop on Computer Science Logic CSL {91}, vol. 626 of LNCS, pp. 396–410. Springer, 1991.

### 1990

• J. Duparc. A hierarchy of Context-free $\omega$-languages. Theoretical Computer Science, 1990.
• E. Grädel. On Solvable Cases of Hilbert's Entscheidungsproblem'. 1990.
• E. Grädel. On the Notion of Linear Time Computability. International Journal of Foundations of Computer Science, vol. 1, pp. 295–307, 1990.
• E. Grädel. Satisfiability of Formulae with one $\forall$ is Decidable in Exponential Time. Archive for Mathematical Logic, vol. 29, pp. 256–276, 1990.
• E. Grädel. Simple Interpretations among Complicated Theories. Information Processing Letters, vol. 35, pp. 235–238, 1990.
• E. Grädel. Domino Games and Complexity. SIAM Journal on Computing, vol. 19, pp. 787–804, 1990.
• M. Otto. Ehrenfeucht-Mostowski Konstruktionen in Erweiterungslogiken. PhD thesis, Freiburg University, 1990.

### 1989

• E. Grädel. Dominoes and the Complexity of Subclasses of Logical Theories. Annals of Pure and Applied Logic, vol. 43, pp. 1–30, 1989.
• E. Grädel. Complexity of Formula Classes in First Order Logic with Functions. In Proceedings of International Conference on Fundamentals of Computation Theory FCT 89, Szeged 1989, vol. 380 of LNCS, pp. 224–233. Springer, 1989.
• E. Grädel. On logical descriptions of some concepts in structural complexity theory. In Proceedings of 3rd Workshop on Computer Science Logic CSL 89, Kaiserslautern, 1989.
• E. Grädel. On the Notion of Linear Time Computability. In Proceedings of 3rd Italian Conference on Theoretical Computer Science, pp. 323–334, Mantova. World Scientific Publishing Co., 1989.

### 1988

• E. Grädel. Subclasses of Presburger Arithmetic and the Polynomial-Time Hierarchy. Theoretical Computer Science, vol. 56, pp. 289–301, 1988.
• E. Grädel. Domino-Games, with an Application to the Complexity of Boolean Algebras with Bounded Quantifier Alternation. In Proceedings of 5th Annual Symposium on Theoretical Aspects of Computer Science STACS 88, Bordeaux 1988, vol. 294 of LNCS, pp. 98–107. Springer, 1988.
• E. Grädel. Size of Models versus Length of Computations. On Inseparability by Nondeterministic Time Complexity Classes. In Proceedings of 2nd Workshop on Computer Science Logic CSL `88, Duisburg 1988, vol. 385 of LNCS, pp. 118–137. Springer, 1988.

### 1987

• E. Grädel. The Complexity of Subclasses of Logical Theories. PhD thesis, Universität Basel, 1987.
• M. Otto. A Reduction Scheme for Phase Spaces with Almost-K{ähler Symmetry – Regularity Results for Momentum Level Sets}. Journal of Geometry and Physics, vol. 4, pp. 101–118, 1987.