Publikationen

Erich Grädel

2024

  • S. Brinke, E. Grädel, and L. Mrkonjić. Ehrenfeucht-Fraïssé Games in Semiring Semantics. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) (A. Murano and A. Silva, Eds.), vol. 288 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 19:1–19:22, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.             
  • E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. Logical Methods in Computer Science, vol. 20(1), 2024.             

2023

  • C. Bizière, E. Grädel, and M. Naaf. Locality Theorems in Semiring Semantics. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (J. Leroux, S. Lombardy, and D. Peleg, Eds.), vol. 272 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 20:1–20:15, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.             
  • C. Bizière, E. Grädel, and M. Naaf. Locality Theorems in Semiring Semantics. arXiv:2303.12627 [cs.LO], full version of MFCS'23 paper, 2023.             
  • S. Brinke, E. Grädel, and L. Mrkonjić. Ehrenfeucht-Fraïssé Games in Semiring Semantics. arXiv:2308.04910 [cs.LO], full version of CSL'24 paper, 2023.             

2022

  • R. Albert and E. Grädel. Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence. Annals of Pure and Applied Logic, vol. 173(10), pp. 103088, 2022.             
  • A. Dawar, E. Grädel, and M. Lichter. Limitations of the invertible-map equivalences. Journal of Logic and Computation, 2022.             
  • E. Grädel, H. Helal, M. Naaf, and R. Wilke. Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022) (C. Baier and D. Fisman, Eds.), pp. 41:1–41:12. ACM, 2022.             
  • E. Grädel, H. Helal, M. Naaf, and R. Wilke. Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics. arXiv:2203.03425 [cs.LO], full version of LICS'22 paper, 2022.             
  • E. Grädel and R. Wilke. Logics with Multiteam Semantics. ACM Transations on Computational Logic, vol. 23(2), pp. 13:1–13:30, 2022.             
  • D. Haase, E. Grädel, and R. Wilke. Separation logic and logics with team semantics. Annals of Pure and Applied Logic, vol. 173(10), pp. 103063, 2022.             

2021

  • R. Albert and E. Grädel. Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence. arXiv:2102.10931 [cs.LO], preprint of APAL journal version, 2021.             
  • K. M. Dannert and E. Grädel. Semiring Provenance for Guarded Logics. In Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory through Algebraic Logic (J. Madarász and G. Székely, Eds.), Outstanding Contribution to Logic, pp. 53–79. Springer, 2021.             
  • K. M. Dannert, E. Grädel, M. Naaf, and V. Tannen. Semiring Provenance for Fixed-Point Logic. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) (C. Baier and J. Goubault-Larrecq, Eds.), vol. 183 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 17:1–17:22, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.             
  • A. Dawar, E. Grädel, and M. Lichter. Limitations of the Invertible-Map Equivalences. arXiv:2109.07218 [cs.LO], 2021.             
  • E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. In Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021) (P. Ganty and D. Bresolin, Eds.), vol. 346 of EPTCS, pp. 67–82, 2021.             
  • E. Grädel, N. Lücking, and M. Naaf. Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials. arXiv:2106.12892 [cs.LO], full version of GandALF'21 paper, 2021.             
  • E. Grädel and L. Mrkonjić. Elementary equivalence versus isomorphism in semiring semantics. arXiv:2102.05473 [math.LO], preprint of ICALP'21 paper, 2021.             
  • E. Grädel and L. Mrkonjić. Elementary Equivalence Versus Isomorphism in Semiring Semantics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (N. Bansal, E. Merelli, and J. Worrell, Eds.), vol. 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 133:1–133:20, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.             
  • E. Grädel and P. Pützstück. Logics of dependence and independence: The local variants. Journal of Logic and Computation, vol. 31(7), pp. 1690-1715, 2021.             
  • E. Grädel and P. Pützstück. Logics of Dependence and Independence: The Local Variants. arXiv:2102.10368 [cs.LO], preprint of journal article, 2021.             

2020

  • A. Dawar, E. Grädel, and M. Hoelzel. Convergence and Nonconvergence Laws for Random Expansions of Product Structures. In Fields of Logic and Computation III (A. Blass, P. Cégielski, N. Dershowitz, M. Droste, and B. Finkbeiner, Eds.), pp. 118–132. Springer, 2020.             
  • E. Grädel. Automatic Structures: Twenty Years Later. In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pp. 21–34. ACM, 2020.             
  • E. Grädel, D. Haase, and R. Wilke. Separation Logic and Logics with Team Semantics. In Workshop on Logics of Dependence and Independence (J. Väänänen and F. Yang, Eds.), 2020.             
  • E. Grädel and M. Otto. Guarded Teams: The Horizontally Guarded Case. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) (M. Fernández and A. Muscholl, Eds.), vol. 152 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 22:1–22:17, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020.             
  • E. Grädel and V. Tannen. Provenance Analysis for Logic and Games. Moscow Journal of Combinatorics and Number Theory, vol. 9(3), pp. 203–228, 2020.             
  • E. Grädel and R. Wilke. Logics with Multiteam Semantics. arXiv:2011.09834 [cs.LO], 2020.             

2019

  • K. M. Dannert and E. Grädel. Provenance Analysis: A Perspective for Description Logics? In Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, vol. 11560 of Lecture Notes in Computer Science, pp. 266–285. Springer, 2019.             
  • K. M. Dannert, E. Grädel, M. Naaf, and V. Tannen. Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic. arXiv:1910.07910 [cs.LO], 2019.             
  • A. Dawar, E. Grädel, and W. Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, Eds.), vol. 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 112:1–112:14, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.             
  • A. Dawar, E. Grädel, and W. Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. arXiv:1902.06648 [cs.LO], 2019.             
  • E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity. Logical Methods in Computer Science, vol. Volume 15, Issue 1, 2019.             
  • E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! The Journal of Symbolic Logic, vol. 84(1), 2019.             
  • E. Grädel and S. Schalthöfer. Choiceless Logarithmic Space. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (P. Rossmanith, P. Heggernes, and J. Katoen, Eds.), vol. 138 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 31:1–31:15, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.             

2018

  • E. Grädel and M. Hoelzel. Dependency Concepts up to Equivalence. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) (D. Ghica and A. Jung, Eds.), vol. 119 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 25:1–25:21, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 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.             
  • 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

  • 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.             

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.             

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.             
  • 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.             

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.                                 
  • 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.                                 
  • 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.             

2011

  • K. Apt and E. Grädel (Eds.). Lectures in Game Theory for Computer Scientists. Cambridge University Press, 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.             
  • E. Grädel. Back and Forth Between Logics and Games. In Lectures in Game Theory for Computer Scientists, pp. 99–145. Springer, 2011.             

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.                                 

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.                                 

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.                                 
  • 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.                                 
  • 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.                                 

2007

  • D. Berwanger, E. Grädel, and G. Lenzi. The variable hierarchy of the μ-calculus is strict. Theory of Computing Systems, vol. 40, pp. 437–466, 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.             

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.                                 

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.                                 

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.             

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.                                 
  • 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.             

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.                                 
  • 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.             

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.                                 
  • 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.                                 
  • 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.             

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.                                 
  • 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.                                 

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.             

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.             

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 STACS`97, vol. 1200 of Lecture Notes in Computer Science, pp. 249–260, 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.             

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.             
  • 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.             

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.             
  • 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.                                 

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.                                 

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.             

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.             

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 ∀ 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.             

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.