Erich Grädel

According to our database1, Erich Grädel authored at least 108 papers between 1987 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
A Finite-Model-Theoretic View on Propositional Proof Complexity.
Logical Methods in Computer Science, 2019

Rank Logic is dead, Long Live Rank Logic!
J. Symb. Log., 2019

Logics for Dependence and Independence (Dagstuhl Seminar 19031).
Dagstuhl Reports, 2019

Approximations of Isomorphism and Logics with Linear-Algebraic Operators.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Provenance Analysis: A Perspective for Description Logics?
Proceedings of the Description Logic, Theory Combination, and All That, 2019

2018
Dependency Concepts up to Equivalence.
Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017
Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).
Dagstuhl Reports, 2017

Definability of summation problems for Abelian groups and semigroups.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Advice Automatic Structures and Uniformly Automatic Classes.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

The Model-Theoretic Expressiveness of Propositional Proof Systems.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
Counting in Team Semantics.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Games for Inclusion Logic and Fixed-Point Logic.
Proceedings of the Dependence Logic, Theory and Applications, 2016

2015
Logics for Dependence and Independence (Dagstuhl Seminar 15261).
Dagstuhl Reports, 2015

Characterising Choiceless Polynomial Time with First-Order Interpretations.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Defining Winning Strategies in Fixed-Point Logic.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Rank Logic is Dead, Long Live Rank Logic!.
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

Is Polynomial Time Choiceless?
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.
Theor. Comput. Sci., 2014

Model-Theoretic Properties of ω-Automatic Structures.
Theory Comput. Syst., 2014

Choiceless Polynomial Time on Structures with Small Abelian Colour Classes.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Bisimulation Safe Fixed Point Logic.
Proceedings of the Advances in Modal Logic 10, 2014

The Freedoms of (Guarded) Bisimulation.
Proceedings of the Johan van Benthem on Logic and Information Dynamics, 2014

2013
Model-checking games for logics of imperfect information.
Theor. Comput. Sci., 2013

Dependence and Independence.
Studia Logica, 2013

Definability of linear equation systems over groups and rings
Logical Methods in Computer Science, 2013

2012
Entanglement and the complexity of directed graphs.
Theor. Comput. Sci., 2012

The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
Proceedings of the Proceedings Third International Symposium on Games, 2012

The Field of Reals is not omega-Automatic.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

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

Banach-Mazur Games with Simple Winning Strategies.
Proceedings of the Computer Science Logic (CSL'12), 2012

Definability of linear equation systems over groups and rings.
Proceedings of the Computer Science Logic (CSL'12), 2012

2010
Model Checking Games for the Quantitative µ-Calculus.
Theory Comput. Syst., 2010

Properties of Almost All Graphs and Generalized Quantifiers.
Fundam. Inform., 2010

Definability in Games.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009
Directed Graphs of Entanglement Two.
Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

2008
Model Checking Games for the Quantitative µ-Calculus.
Proceedings of the STACS 2008, 2008

Banach-Mazur Games on Graphs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

The Descriptive Complexity of Parity Games.
Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

2007
Finite Model Theory and Its Applications
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-68804-4, 2007

The Variable Hierarchy of the µ-Calculus Is Strict.
Theory Comput. Syst., 2007

2006
Positional Determinacy of Games with Infinitely Many Priorities.
Logical Methods in Computer Science, 2006

The Ackermann Award 2006.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005
The Ackermann Award 2005.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004
Finite Presentations of Infinite Structures: Automata and Interpretations.
Theory Comput. Syst., 2004

Fixed-Point Logics and Solitaire Games.
Theory Comput. Syst., 2004

Positional Determinacy of Infinite Games.
Proceedings of the STACS 2004, 2004

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

Backtracking Games and Inflationary Fixed Points.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
LICS 2001 special issue.
ACM Trans. Comput. Log., 2003

Once upon a Time in a West - Determinacy, Definability, and Complexity of Path Games.
Proceedings of the Logic for Programming, 2003

Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Quantum Computing and Abstract State Machines.
Proceedings of the Abstract State Machines, 2003

2002
Datalog LITE: a deductive query language with linear time model checking.
ACM Trans. Comput. Log., 2002

Guarded fixed point logics and the monadic theory of countable trees.
Theor. Comput. Sci., 2002

Model Checking Games.
Electr. Notes Theor. Comput. Sci., 2002

On the Variable Hierarchy of the Modal µ-Calculus.
Proceedings of the Computer Science Logic, 16th International Workshop, 2002

2001
Games and Model Checking for Guarded Logics.
Proceedings of the Logic for Programming, 2001

Inflationary Fixed Points in Modal Logic.
Proceedings of the Computer Science Logic, 15th International Workshop, 2001

Why are Modal Logics so Robustly Decidable?
Current Trends in Theoretical Computer Science, 2001

2000
Efficient Evaluation Methods for Guarded Logics and Datalog LITE.
Proceedings of the Logic for Programming and Automated Reasoning, 2000

Back and Forth between Guarded and Modal Logics.
Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000

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

Decidability issues for action guarded logics.
Proceedings of the 2000 International Workshop on Description Logics (DL2000), 2000

1999
On Logics with Two Variables.
Theor. Comput. Sci., 1999

On Preservation Theorems for Two-Variable Logic.
Math. Log. Q., 1999

On The Restraining Power of Guards.
J. Symb. Log., 1999

Why are Modal Logics so Robustly Decidable?
Bulletin of the EATCS, 1999

0-1 laws for recursive structures.
Arch. Math. Log., 1999

Guarded Fixed Point Logic.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Two-Variable Descriptions of Regularity.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Logspace Reducibility via Abstract State Machines.
Proceedings of the FM'99 - Formal Methods, 1999

Descriptive Complexity Theory for Constraint Databases.
Proceedings of the Computer Science Logic, 13th International Workshop, 1999

Invited Talk: Decision procedures for guarded logics.
Proceedings of the Automated Deduction, 1999

1998
The Complexity of Query Reliability.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

Description Logics and Guarded Fragments of First Order Logic.
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.
Bulletin of Symbolic Logic, 1997

Undecidability Results on Two-Variable Logics.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Two-Variable Logic with Counting is Decidable.
Proceedings of the Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29, 1997

The Classical Decision Problem
Perspectives in Mathematical Logic, Springer, 1997

1996
Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic.
Ann. Pure Appl. Logic, 1996

1995
On the Power of Deterministic Transitive Closures
Inf. Comput., May, 1995

Tailoring Recursion for Complexity.
J. Symb. Log., 1995

Descriptive complexity theory over the real numbers.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Generalized Quantifiers and 0-1 Laws
Proceedings of the Proceedings, 1995

1994
Definability on finite structures and the existence of one-way functions.
Meth. of Logic in CS, 1994

Metafinite Model Theory.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Tailoring Recursing for Complexity.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Logical Definability of Counting Functions.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
Approximable Minimization Problems and Optimal Solutions on Random Inputs.
Proceedings of the Computer Science Logic, 7th Workshop, 1993

1992
Deterministic vs. Nondeterministic Transitive Closure Logic
Proceedings of the Seventh Annual Symposium on Logic in Computer Science (LICS '92), 1992

Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Inductive Definability with Counting on Finite Structures.
Proceedings of the Computer Science Logic, 6th Workshop, 1992

Optimization Problems: Expressibility, Approximation Properties and Expected Asymptotic Growth of Optimal Solutions.
Proceedings of the Computer Science Logic, 6th Workshop, 1992

1991
Simple Sentences That Are Hard to Decide
Inf. Comput., September, 1991

The Expressive Power of Second Order Horn Logic.
Proceedings of the STACS 91, 1991

On Transitive Closure Logic.
Proceedings of the Computer Science Logic, 5th Workshop, 1991

Capturing Complexity Classes by Fragments of Second Order Logic.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
Domino Games and Complexity.
SIAM J. Comput., 1990

Simple Interpretations Among Complicated Theories.
Inf. Process. Lett., 1990

On the Notion of Linear Time Computability.
Int. J. Found. Comput. Sci., 1990

Satisfiability of formulae with one ∀ is decidable in exponential time.
Arch. Math. Log., 1990

1989
Dominoes and the Complexity of Subclasses of Logical Theories.
Ann. Pure Appl. Logic, 1989

Complexity of Formula Classes in First Order Logic with Functions.
Proceedings of the Fundamentals of Computation Theory, 1989

On Logical Descriptions of Some Concepts in Structural Complexity Theory.
Proceedings of the CSL '89, 1989

1988
Subclasses of Presburger Arithmetic and the Polynomial-Time Hierarchy.
Theor. Comput. Sci., 1988

Domino Games with an Application to the Complexity of Boolean Algebras with Bounded Quantifier Alternations.
Proceedings of the STACS 88, 1988

Size of Models versus Length of Computations: On Inseparability by Nondeterministic Time Complexity Classes.
Proceedings of the CSL '88, 1988

1987
The complexity of subclasses of logical theories.
PhD thesis, 1987


  Loading...