Publications
Erich Grädel
2018

E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A FiniteModelTheoretic 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.

E. Grädel, B. Pago, and W. Pakusa. The ModelTheoretic 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 FirstOrder 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–LeibnizZentrum fuer Informatik, 2016.

E. Grädel. Games for Inclusion Logic and FixedPoint 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 fixedpoint 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. 193209. Springer, 2015.

E. Grädel, Ł. Kaiser, W. Pakusa, and S. Schalthöfer. Characterising Choiceless Polynomial Time with FirstOrder 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. 5062. 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. 331. 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. ModelTheoretic Properties of omegaAutomatic 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. ModelChecking 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. 399410, 2013.
2012

F. Abu Zaid, E. Grädel, and Ł. Kaiser. The Field of Reals is not omegaAutomatic. 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–LeibnizZentrum 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. BanachMazur 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–LeibnizZentrum 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.
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 muCalculus. Theory Comput. Syst., vol. 47(3), pp. 696–719, 2010.
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 $\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.

E. Grädel. {BanachMazur 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 – LeibnizZentrum 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.
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. FixedPoint 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 firstorder and fixedpoint logic. {From prefixvocabulary 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 NonMonotone 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 LogicBased 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. 01 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 TwoVariable Logics. Archive for Mathematical Logic, vol. 38, pp. 213–354, 1999.

E. Grädel and E. Rosen. Preservation theorems for twovariable logic. Mathematical Logic Quarterly, vol. 45, pp. 315–325, 1999.

E. Grädel and E. Rosen. Twovariable 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 firstorder 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 TwoVariable FirstOrder Logic. Bulletin of Symbolic Logic, vol. 3, pp. 53–69, 1997.

E. Grädel, M. Otto, and E. Rosen. TwoVariable 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 TwoVariable 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 01 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 ACMSymposium 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 OneWay 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 $\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.
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 PolynomialTime Hierarchy. Theoretical Computer Science, vol. 56, pp. 289–301, 1988.

E. Grädel. DominoGames, 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.