Publications

Erich Grädel

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.

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. Games for Inclusion Logic and Fixed-Point Logic, 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 $\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. {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 $\mu$-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 STACS97, 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 $\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 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.