Erich Grädel

According to our database, Erich Grädel authored at least 129 papers between 1987 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Semiring Provenance for B\"uchi Games: Strategy Analysis with Absorptive Polynomials.

Erich Grädel, Niels Lücking, Matthias Naaf

Log. Methods Comput. Sci., 2024

Ehrenfeucht-Fraïssé Games in Semiring Semantics.

Sophie Brinke, Erich Grädel, Lovro Mrkonjic

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

Semiring Provenance in the Infinite.

Sophie Brinke, Erich Grädel, Lovro Mrkonjic, Matthias Naaf

Proceedings of the Provenance of Elegance in Computation - Essays Dedicated to Val Tannen, 2024

2023

Limitations of the invertible-map equivalences.

Anuj Dawar, Erich Grädel, Moritz Lichter

J. Log. Comput., July, 2023

Locality Theorems in Semiring Semantics.

Clotilde Bizière, Erich Grädel, Matthias Naaf

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

Logics with Multiteam Semantics.

Erich Grädel, Richard Wilke

ACM Trans. Comput. Log., 2022

Logic and Random Discrete Structures (Dagstuhl Seminar 22061).

Erich Grädel, Phokion G. Kolaitis, Marc Noy

Dagstuhl Reports, 2022

Separation logic and logics with team semantics.

Darion Haase, Erich Grädel, Richard Wilke

Ann. Pure Appl. Log., 2022

Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence.

Rafael Albert, Erich Grädel

Ann. Pure Appl. Log., 2022

Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics.

Erich Grädel, Hayyan Helal, Matthias Naaf, Richard Wilke

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

2021

Logics of dependence and independence: The local variants.

Erich Grädel, Phil Pützstück

J. Log. Comput., 2021

Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials.

Erich Grädel, Niels Lücking, Matthias Naaf

Proceedings of the Proceedings 12th International Symposium on Games, 2021

Elementary Equivalence Versus Isomorphism in Semiring Semantics.

Erich Grädel, Lovro Mrkonjic

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Semiring Provenance for Fixed-Point Logic.

Katrin M. Dannert, Erich Grädel, Matthias Naaf, Val Tannen

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

2020

Automatic Structures: Twenty Years Later.

Erich Grädel

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Guarded Teams: The Horizontally Guarded Case.

Erich Grädel, Martin Otto

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

Convergence and Nonconvergence Laws for Random Expansions of Product Structures.

Anuj Dawar, Erich Grädel, Matthias Hoelzel

Proceedings of the Fields of Logic and Computation III, 2020

2019

A Finite-Model-Theoretic View on Propositional Proof Complexity.

Erich Grädel, Martin Grohe, Benedikt Pago, Wied Pakusa

Log. Methods Comput. Sci., 2019

Rank Logic is dead, Long Live Rank Logic!

Erich Grädel, Wied Pakusa

J. Symb. Log., 2019

Logics for Dependence and Independence (Dagstuhl Seminar 19031).

Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, Heribert Vollmer

Dagstuhl Reports, 2019

Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic.

Katrin M. Dannert, Erich Grädel, Matthias Naaf, Val Tannen

CoRR, 2019

Provenance Analysis for Logic and Games.

Erich Grädel, Val Tannen

CoRR, 2019

Choiceless Logarithmic Space.

Erich Grädel, Svenja Schalthöfer

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Approximations of Isomorphism and Logics with Linear-Algebraic Operators.

Anuj Dawar, Erich Grädel, Wied Pakusa

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Provenance Analysis: A Perspective for Description Logics?

Katrin M. Dannert, Erich Grädel

Proceedings of the Description Logic, Theory Combination, and All That, 2019

2018

Dependency Concepts up to Equivalence.

Erich Grädel, Matthias Hoelzel

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).

Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, Thomas Schwentick

Dagstuhl Reports, 2017

Semiring Provenance for First-Order Model Checking.

Erich Grädel, Val Tannen

CoRR, 2017

Definability of summation problems for Abelian groups and semigroups.

Faried Abu Zaid, Anuj Dawar, Erich Grädel, Wied Pakusa

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Advice Automatic Structures and Uniformly Automatic Classes.

Faried Abu Zaid, Erich Grädel, Frederic Reinhardt

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

The Model-Theoretic Expressiveness of Propositional Proof Systems.

Erich Grädel, Benedikt Pago, Wied Pakusa

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Counting in Team Semantics.

Erich Grädel, Stefan Hegselmann

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Games for Inclusion Logic and Fixed-Point Logic.

Erich Grädel

Proceedings of the Dependence Logic, Theory and Applications, 2016

2015

Logics for Dependence and Independence (Dagstuhl Seminar 15261).

Erich Grädel, Juha Kontinen, Jouko Väänänen, Heribert Vollmer

Dagstuhl Reports, 2015

Characterising Choiceless Polynomial Time with First-Order Interpretations.

Erich Grädel, Wied Pakusa, Svenja Schalthöfer, Lukasz Kaiser

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Defining Winning Strategies in Fixed-Point Logic.

Felix Canavoi, Erich Grädel, Simon Leßenich, Wied Pakusa

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Is Polynomial Time Choiceless?

Erich Grädel, Martin Grohe

Proceedings of the Fields of Logic and Computation II, 2015

2014

The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs.

Felix Canavoi, Erich Grädel, Roman Rabinovich

Theor. Comput. Sci., 2014

Model-Theoretic Properties of ω-Automatic Structures.

Faried Abu Zaid, Erich Grädel, Lukasz Kaiser, Wied Pakusa

Theory Comput. Syst., 2014

Choiceless Polynomial Time on Structures with Small Abelian Colour Classes.

Faried Abu Zaid, Erich Grädel, Martin Grohe, Wied Pakusa

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Bisimulation Safe Fixed Point Logic.

Faried Abu Zaid, Erich Grädel, Stephan Jaax

Proceedings of the Advances in Modal Logic 10, 2014

The Freedoms of (Guarded) Bisimulation.

Erich Grädel, Martin Otto

Proceedings of the Johan van Benthem on Logic and Information Dynamics, 2014

2013

Model-checking games for logics of imperfect information.

Erich Grädel

Theor. Comput. Sci., 2013

Dependence and Independence.

Erich Grädel, Jouko A. Väänänen

Stud Logica, 2013

Definability of linear equation systems over groups and rings

Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, Wied Pakusa

Log. Methods Comput. Sci., 2013

2012

Entanglement and the complexity of directed graphs.

Dietmar Berwanger, Erich Grädel, Lukasz Kaiser, Roman Rabinovich

Theor. Comput. Sci., 2012

The Field of Reals is not omega-Automatic.

Faried Abu Zaid, Erich Grädel, Lukasz Kaiser

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Dynamic definability.

Erich Grädel, Sebastian Siebertz

Proceedings of the 15th International Conference on Database Theory, 2012

Banach-Mazur Games with Simple Winning Strategies.

Erich Grädel, Simon Leßenich

Proceedings of the Computer Science Logic (CSL'12), 2012

2011

Back and forth between logic and games.

Erich Grädel

Proceedings of the Lectures in Game Theory for Computer Scientists., 2011

Automata-based presentations of infinite structures.

Vince Bárány, Erich Grädel, Sasha Rubin

Proceedings of the Finite and Algorithmic Model Theory., 2011

2010

Model Checking Games for the Quantitative <i>µ</i>-Calculus.

Diana Fischer, Erich Grädel, Lukasz Kaiser

Theory Comput. Syst., 2010

Properties of Almost All Graphs and Generalized Quantifiers.

Anuj Dawar, Erich Grädel

Fundam. Informaticae, 2010

Definability in Games.

Erich Grädel

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009

Directed Graphs of Entanglement Two.

Erich Grädel, Lukasz Kaiser, Roman Rabinovich

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

2008

Model Checking Games for the Quantitative mu-Calculus

Diana Fischer, Erich Grädel, Lukasz Kaiser

CoRR, 2008

Model Checking Games for the Quantitative µ-Calculus.

Diana Fischer, Erich Grädel, Lukasz Kaiser

Proceedings of the STACS 2008, 2008

Banach-Mazur Games on Graphs.

Erich Grädel

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

The Descriptive Complexity of Parity Games.

Anuj Dawar, Erich Grädel

Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

2007

Finite Model Theory and Its Applications

Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-68804-4, 2007

The Variable Hierarchy of the µ-Calculus Is Strict.

Dietmar Berwanger, Erich Grädel, Giacomo Lenzi

Theory Comput. Syst., 2007

2006

Backtracking games and inflationary fixed points.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

Theor. Comput. Sci., 2006

Positional Determinacy of Games with Infinitely Many Priorities.

Erich Grädel, Igor Walukiewicz

Log. Methods Comput. Sci., 2006

The Ackermann Award 2006.

Samson Abramsky, Erich Grädel, Johann A. Makowsky

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005

The Ackermann Award 2005.

Erich Grädel, Janos Makowsky, Alexander A. Razborov

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004

Inflationary fixed points in modal logic.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

ACM Trans. Comput. Log., 2004

Finite Presentations of Infinite Structures: Automata and Interpretations.

Achim Blumensath, Erich Grädel

Theory Comput. Syst., 2004

Fixed-Point Logics and Solitaire Games.

Dietmar Berwanger, Erich Grädel

Theory Comput. Syst., 2004

Positional Determinacy of Infinite Games.

Erich Grädel

Proceedings of the STACS 2004, 2004

Entanglement - A Measure for the Complexity of Directed Graphs with Applications to Logic and Games.

Dietmar Berwanger, Erich Grädel

Proceedings of the Logic for Programming, 2004

2003

LICS 2001 special issue.

Erich Grädel, Joseph Y. Halpern, Radha Jagadeesan, Adolfo Piperno

ACM Trans. Comput. Log., 2003

Once upon a Time in a West - Determinacy, Definability, and Complexity of Path Games.

Dietmar Berwanger, Erich Grädel, Stephan Kreutzer

Proceedings of the Logic for Programming, 2003

Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions.

Erich Grädel, Stephan Kreutzer

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Inflationary and Deflationary Fixed Points (Invited Talk).

Erich Grädel

Proceedings of the FICS '03, 2003

Quantum Computing and Abstract State Machines.

Erich Grädel, Antje Nowack

Proceedings of the Abstract State Machines, 2003

2002

Back and forth between guarded and modal logics.

Erich Grädel, Colin Hirsch, Martin Otto

ACM Trans. Comput. Log., 2002

Datalog LITE: a deductive query language with linear time model checking.

Georg Gottlob, Erich Grädel, Helmut Veith

ACM Trans. Comput. Log., 2002

Guarded fixed point logics and the monadic theory of countable trees.

Erich Grädel

Theor. Comput. Sci., 2002

Model Checking Games.

Erich Grädel

Proceedings of the 9th Workhop on Logic, Language, Information and Computation, 2002

On the Variable Hierarchy of the Modal µ-Calculus.

Dietmar Berwanger, Erich Grädel, Giacomo Lenzi

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

2001

Games and Model Checking for Guarded Logics.

Dietmar Berwanger, Erich Grädel

Proceedings of the Logic for Programming, 2001

Why are Modal Logics so Robustly Decidable?

Erich Grädel

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

Efficient Evaluation Methods for Guarded Logics and Datalog LITE.

Erich Grädel

Proceedings of the Logic for Programming and Automated Reasoning, 2000

Automatic Structures.

Achim Blumensath, Erich Grädel

Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000

Decidability issues for action guarded logics.

M.-Elisabeth Goncalves, Erich Grädel

Proceedings of the 2000 International Workshop on Description Logics (DL2000), 2000

1999

On Logics with Two Variables.

Erich Grädel, Martin Otto

Theor. Comput. Sci., 1999

On Preservation Theorems for Two-Variable Logic.

Erich Grädel, Eric Rosen

Math. Log. Q., 1999

On The Restraining Power of Guards.

Erich Grädel

J. Symb. Log., 1999

Why are Modal Logics so Robustly Decidable?

Erich Grädel

Bull. EATCS, 1999

Undecidability results on two-variable logics.

Erich Grädel, Martin Otto, Eric Rosen

Arch. Math. Log., 1999

0-1 laws for recursive structures.

Erich Grädel, Anders Malmström

Arch. Math. Log., 1999

Guarded Fixed Point Logic.

Erich Grädel, Igor Walukiewicz

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Two-Variable Descriptions of Regularity.

Erich Grädel, Eric Rosen

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Logspace Reducibility via Abstract State Machines.

Erich Grädel, Marc Spielmann

Proceedings of the FM'99 - Formal Methods, 1999

Descriptive Complexity Theory for Constraint Databases.

Erich Grädel, Stephan Kreutzer

Proceedings of the Computer Science Logic, 13th International Workshop, 1999

Invited Talk: Decision procedures for guarded logics.

Erich Grädel

Proceedings of the Automated Deduction, 1999

1998

Metafinite Model Theory.

Erich Grädel, Yuri Gurevich

Inf. Comput., 1998

The Complexity of Query Reliability.

Erich Grädel, Yuri Gurevich, Colin Hirsch

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

Description Logics and Guarded Fragments of First Order Logic.

Erich Grädel

Proceedings of the 1998 International Workshop on Description Logics (DL'98), IRST, Povo, 1998

1997

On the decision problem for two-variable first-order logic.

Erich Grädel, Phokion G. Kolaitis, Moshe Y. Vardi

Bull. Symb. Log., 1997

Two-Variable Logic with Counting is Decidable.

Erich Grädel, Martin Otto, Eric Rosen

Proceedings of the Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29, 1997

The Classical Decision Problem

Egon Börger, Erich Grädel, Yuri Gurevich

Perspectives in Mathematical Logic, Springer, 1997

1996

Logical Definability of Counting Functions.

Kevin J. Compton, Erich Grädel

J. Comput. Syst. Sci., 1996

Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic.

Erich Grädel, Gregory L. McColm

Ann. Pure Appl. Log., 1996

1995

On the Power of Deterministic Transitive Closures

Erich Grädel, Gregory L. McColm

Inf. Comput., May, 1995

Tailoring Recursion for Complexity.

Erich Grädel, Yuri Gurevich

J. Symb. Log., 1995

Descriptive complexity theory over the real numbers.

Erich Grädel, Klaus Meer

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Generalized Quantifiers and 0-1 Laws

Anuj Dawar, Erich Grädel

Proceedings of the Proceedings, 1995

1994

Definability on finite structures and the existence of one-way functions.

Erich Grädel

Methods Log. Comput. Sci., 1994

Tailoring Recursing for Complexity.

Erich Grädel, Yuri Gurevich

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

1993

Approximable Minimization Problems and Optimal Solutions on Random Inputs.

Erich Grädel, Anders Malmström

Proceedings of the Computer Science Logic, 7th Workshop, 1993

1992

Capturing Complexity Classes by Fragments of Second-Order Logic.

Erich Grädel

Theor. Comput. Sci., 1992

Deterministic vs. Nondeterministic Transitive Closure Logic

Erich Grädel, Gregory L. McColm

Proceedings of the Seventh Annual Symposium on Logic in Computer Science (LICS '92), 1992

Inductive Definability with Counting on Finite Structures.

Erich Grädel, Martin Otto

Proceedings of the Computer Science Logic, 6th Workshop, 1992

Optimization Problems: Expressibility, Approximation Properties and Expected Asymptotic Growth of Optimal Solutions.

Thomas Behrendt, Kevin J. Compton, Erich Grädel

Proceedings of the Computer Science Logic, 6th Workshop, 1992

1991

Simple Sentences That Are Hard to Decide

Erich Grädel

Inf. Comput., September, 1991

The Expressive Power of Second Order Horn Logic.

Erich Grädel

Proceedings of the STACS 91, 1991

On Transitive Closure Logic.

Erich Grädel

Proceedings of the Computer Science Logic, 5th Workshop, 1991

1990

Domino Games and Complexity.

Erich Grädel

SIAM J. Comput., 1990

Simple Interpretations Among Complicated Theories.

Erich Grädel

Inf. Process. Lett., 1990

On the Notion of Linear Time Computability.

Erich Grädel

Int. J. Found. Comput. Sci., 1990

Satisfiability of formulae with one ∀ is decidable in exponential time.

Erich Grädel

Arch. Math. Log., 1990

1989

Dominoes and the Complexity of Subclasses of Logical Theories.

Erich Grädel

Ann. Pure Appl. Log., 1989

Complexity of Formula Classes in First Order Logic with Functions.

Erich Grädel

Proceedings of the Fundamentals of Computation Theory, 1989

On Logical Descriptions of Some Concepts in Structural Complexity Theory.

Erich Grädel

Proceedings of the CSL '89, 1989

1988

Subclasses of Presburger Arithmetic and the Polynomial-Time Hierarchy.

Erich Grädel

Theor. Comput. Sci., 1988

Domino Games with an Application to the Complexity of Boolean Algebras with Bounded Quantifier Alternations.

Erich Grädel

Proceedings of the STACS 88, 1988

Size of Models versus Length of Computations: On Inseparability by Nondeterministic Time Complexity Classes.

Erich Grädel

Proceedings of the CSL '88, 1988

1987

The complexity of subclasses of logical theories.

Erich Grädel

PhD thesis, 1987