Logik
und Theorie
diskreter Systeme

Informatik 7

Martin Grohe's Publications

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
Draft manuscript, 2013.
Color Refinement and its Applications,
with Kristian Kersting, Martin Mladenov, and Pascal Schweitzer, 2017. Preliminary Draft of a Chapter that is to appear in: Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, David Poole, An Introduction to Lifted Probabilistic Inference, Cambridge University Press.
The Hardness of Embedding Grids and Walls,
with Yijia Chen and BingKai Lin. CoRR abs/1703.06423 2017.
Learning first-order definable concepts over structures of small degree,
with Martin Ritzert. CoRR abs/1701.05487, 2017.
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
with Christoph Berkholz. Conference Version in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.327-339, 2017.
Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles).
CoRR abs/1605.06704, 2016.
Quasi-4-Connected Components.
Conference version in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, 2016.
Order Invariance on Decomposable Structures
with Michael Elberfeld and Marlin Frickenschmidt. Conference version in Proceedings of the 31st IEEE Symposium on Logic in Computer Science (LICS 2016), pp.397-406, 2016. 
Computing with Tangles
with Pascal Schweitzer. In SIAM Journal on Discrete Mathematics, 30(2):1213-1247, 2016. Conference Version in Proceedings of the 47th ACM Symposium on Theory of Computing (STOC'15), pp.683-692, 2015.
Where First-Order and Monadic Second-Order Logic Coincide,
with Michael Elberfeld and Till Tantau. In ACM Transactions on Computational Logic, 17(4):25:1-25:18, 2016. Conference version in Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS 2016, pp.265-274, 2012.
Tangles and Connectivity in Graphs
In A.-H. Dediu and J. Janousek and C. Martin-Vide and B. Truthe (Ed.), Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016). Lecture Notes in Computer Science 9618, pp.24-42, 2016.
Colouring and Covering Nowhere Dense Graphs
with S. Kreutzer and R. Rabinovich and S. Siebertz and K. Stavropoulos. Conference Version in Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'15), Lecture Notes in Computer Science 9224, pp.325-338, 2016.
Isomorphism Testing for Graphs of Bounded Rank Width
with Pascal Schweitzer. Conference Version in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS15), pp.1010-1029, 2015.
Is Polynomial Time Choiceless
with Erich Grädel. In L. D. Beklemishev and A. Blass and N. Dershowitz and B. Finkbeiner and W. Schulte (Ed.), Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday. Lecture Notes in Computer Science 9300, pp.193-209, 2015.
Limitations of Algebraic Approaches to Graph Isomorphism Testing
with Christoph Berkholz. Conference version in M.M. Halldorsson and K. Iwama and N. Kobayashi and B. Speckmann, Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), Part II. Lecture Notes in Computer Science 9134, pp.155-166, 2015.
Logical Characterisations of Complexity Classes.
In B. Engquist (Ed), Encyclopedia of Applied and Computational Mathematics, Springer Verlag, 2015.
Pebble Games and Linear Equations,
with Martin Otto. In Journal of Symbolic Logic 80(3), 2015. Conference version in Proceedings of the 26th International Workshop on Computer Science Logic (CSL'12), Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, 2012.
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
with Dániel Marx. In SIAM Journal on Computing 44(1):114-159, 2015. Conference version in Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pp.173-192, 2012.
Constraint Solving via Fractional Edge Covers,
with Dániel Marx. ACM Transactions on Algorithms 11(1), 2014. Conference version in Proceedings of the of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.289-298, 2006.
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes,
with Faried Abu Zaid, Erich Grädel, and Wied Pakusa. In E. Csuhaj-Varjú and M. Dietzfelbinger and Z. Ésik, Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Part I. Lecture Notes in Computer Science 8634, pp.50-62, 2014.
Dimension Reduction via Colour Refinement
with Kristian Kersting and Martin Mladenov and Erkal Selman, 2014. Conference version in A. Schulz and D. Wagner, Proceedings of the 22nd Annual European Symposium on Algorithms. Lecture Notes in Computer Science 8737, pp. 505–516, 2014
Power Iterated Color Refinement
with Kristian Kersting and Martin Mladenov and Roman Garnett. In P. Stone C.E. Brodley, Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp. 1904–1910, 2014.
Decding First-Order properties of Nowhere Dense Graphs
with Stephan Kreutzer and Sebastian Siebertz. Conference version in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC'14), pp.89-98, 2014.
Algorithmic Meta Theorems for Sparse Graph Classes
In E.A. Hirsch and S. Kuznetsov and J.-E. Pin and N.K. Vereshchagin, Proceedings of the 9th International Computer Science Symposium in Russia (CSR'14). Lecture Notes in Computer Science 8476, pp.16-22, 2014.
Monadic Datalog Containment on Trees
with André Frochaux and Nicole Schweikardt. Conference version in G. Gottlob and J. Pérez, Proceedings of the 8th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW'14), 2014.
Size bounds and query plans for relational joins,
with Albert Atserias and Dániel Marx. SIAM Journal on Computing 42(4):1737-1767, 2013. Conference version in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008.
Characterisations of Nowhere Dense Graphs
with Stephan Kreutzer and Sebastian Siebertz. In A. Seth and N.K. Vishnoi, Proceedings of the 32nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). LIPICS - Leibniz International Proceedings in Informatics 24, pp.21-40, 2013.
 
Bounds and Algorithms for Joins via Fractional Edge Covers.
In V. Tannen and L. Wong and L. Libkin and W. Fan and W.-C. Tan and M. Fourman, In Search of Elegance in the Theory and Practice of Computation, Essays Dedicated to Peter Buneman. Lecture Notes in Computer Science 8000, pp.321-338, 2013.
 
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement,
with Paul Bonsma and Christoph Berkholz. Conference version in H.L. Bodlaender and G.F. Italiano (Ed.), Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), Lecture Notes in Computer Science 8125, pp.145-156, 2013.
 
A Simple Algorithm for the Graph Minor Decomposition — Logic Meets Structural Graph Theory —
with Ken-ichi Kawarabayashi and Bruce Reed. In Proceedings of the of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp.414-431, 2013.
 
Fixed-Point Definability and Polynomial Time on Graph with Excluded Minors,
Journal of the ACM 59(5), 2012. Conference version in Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10), 2010.
 
Enumerating Homomorphisms,
with Andrei A. Bulatov, Victor Dalmau, and Dániel Marx. Journal of Computer and System Sciences 78:638-650, 2012. Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.231-242, 2009.
 
L-Recursion and a new Logic for Logarithmic Space,
with Berit Grußien, André Hernich, and Bastian Laubner. Logical Methods in Computer Science 9(1), 2012. Conference Version in Proceedings of the 25th International Workshop on Computer Science Logic (CSL'11), Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, 2011.
 
Cover  Model Theoretic Methods in Finite Combinatorics,
edited jointly with Janos Makowsky. Contemporary Mathematics 558, American Mathematical Society, 2011.
 
Methods for Algorithmic Meta Theorems,
with Stephan Kreutzer, 2011. In Martin Grohe, Johann Makowsky (Eds), Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011.
 
Counting Homomorphisms and Partition Functions,
with Marc Thurley, 2011. In Martin Grohe, Johann Makowsky (Eds), Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011.
 
From Polynomial Time Queries to Graph Structure Theory.
In Communications of the ACM 54(6):104-112, 2011.
 
Finding Topological Subgraphs is Fixed-Parameter Tractable,
with Dániel Marx, Ken-Ich Kawarbayashi, and Paul Wollan. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pp.479-488, 2011.
 
Randomisation and Derandomisation in Descriptive Complexity Theory,
with Kord Eickmeyer. Logical Methods in Computer Science, Volume 7, Issue 3, 2011.
Conference version in Proceedings of the 24th International Workshop on Computer Science Logic (CSL'10), pp.275-289, 2010.
 
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs,
In A. Blass and N. Dershowitz and W. Reisig (Ed.), Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, Lecture Notes in Computer Science 6300, pp.328-353, 2010.
 
A complexity dichotomy for partition functions with mixed signs,
with Leslie Ann Goldberg, Mark Jerrum, and Marc Thurley. SIAM Journal on Computing 39:336-402, 2010.
Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.493-504, 2009.
 
Constraint satisfaction problems with succinctly specified relations,
with Hubie Chen. Journal of Computer and System Sciences 76(8):847-860, 2010.
 
Fixed-Point Definability and Polynomial Time.
In Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.20-23, 2009. Slides of my CSL-talk.
 
Logics with Rank Operators,
with Anuj Dawar, Bjarki Holm, and Bastian Laubner. In Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS'09), pp.113-122, 2009.
 
Lower bounds for processing data with few random accesses to external memory,
with Andre Hernich and Nicole Schweikardt. Journal of the ACM, 56(3), 2009. Full version of PODS'05 and PODS'06 papers.
 
Database query processing using finite cursor machines,
with Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche. Theory of Computing Systems, 44:533-560, 2009.
Conference version in In Proceedings of the 11th International Conference on Database Theory (ICDT'07), Lecture Notes in Computer Science 4353, pp.284-298, 2007.
 
The Complexity of Datalog on Linear Orders,
with Götz Schwandtner. Logical Methods in Computer Science, 5(1), 2009.
 
On tree width, bramble size, and expansion,
with Dániel Marx. Journal of Combinatorial Theory, Series B 99:218-228, 2009.
 
Preservation under Extensions on Well-Behaved Finite Structures,
with Albert Atserias and Anuj Dawar. SIAM Journal on Computing, 38:1364-1381, 2008.
Conference version appeared in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp.1437-1450, 2005. (Abstract)
 
Non-dichotomies in constraint satisfaction complexity,
with Manuel Bodirsky. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track B), Lecture Notes in Computer Science 5126, pp.184-196, 2008.
 
Definable tree decompositions.
In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008.
 
The quest for a logic capturing PTIME.
In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267-271, 2008.
 
Approximation of natural W[P]-complete minimisation problems is hard,
with Kord Eickmeyer and Magdalena Grüber. In Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008.
 
Computing excluded minors,
with Isolde Adler and Stephan Kreutzer. In Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.641-650, 2008.
 
Logic, graphs, and algorithms.
In J.Flum, E.Grädel, T.Wilke (Eds), Logic and Automata – History and Perspectives, Amsterdam University Press, 2007.
 
An Isomorphism between Subexponential and Parameterized Complexity Theory,
with Yijia Chen. SIAM Journal on Computing 37:1228-1258, 2007. Conference version in Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006.
 
Bounded Fixed-Parameter Tractability and Reducibility,
with Rod Downey, Jörg Flum, and Mark Weyer. Annals of Pure and Applied Logic 148:1-19, 2007.
 
Parameterized Approximability of the Disjoint Cycle Problem ,
with Magdalena Grüber. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A), Lecture Notes in Computer Science 4596, pp.363-374, 2007.
 
Model Theory Makes Formulas Large,
with Anuj Dawar, Stephan Kreutzer and Nicole Schweikardt. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track B), Lecture Notes in Computer Science 4596, pp.913-924, 2007.
 
Locally Excluding a Minor,
with Anuj Dawar and Stephan Kreutzer. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science (LICS'07), pp.270-279, 2007.
 
The complexity of homomorphism and constraint satisfaction problems seen from the other side.
Journal of the ACM, 54(1), 2007. Conference version in Proceedings of the 44th IEEE Symposium on Foundations of Comupter Science (FOCS'03), pp.552-561, 2003. (Abstract)
 
Hypertree-Width and Related Hypergraph Invariants,
with Isolde Adler and Georg Gottlob. European Journal of Combinatorics, 28:2167-2181, 2007.
Conference version in Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05), DMTCS Proceedings Series, Volume AE, pp.5-10, 2005.
 
Tight Lower Bounds for Query Processing on Streaming and External Memory Data External Memory,
with Christoph Koch and Nicole Schweikardt. Theoretical Computer Science 380:199-217, 2007. Conference version in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp.1076-1088, 2005. (Abstract)
 
An analysis of the W*-hierarchy,
with Yijia Chen and Jörg Flum. Journal of Symbolic Logic 72:513-534, 2007.
 
On parameterized approximability ,
with Yijia Chen and Magdalena Grüber. Conference version appeared in Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science 4169, pp.109-120, 2006.
 
Approximation Schemes for First-Order Definable Optimisation Problems ,
with Anuj Dawar, Stephan Kreutzer, and Nicole Schweikardt. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411-420, 2006.
 
The structure of tractable constraint satisfaction problems .
In Proceedings of the 31st Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 4162, pp.58-72, 2006.
 
Testing Graph Isomorphism in Parallel by Playing a Game ,
with Oleg Verbitzky. Conference version in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I, Lecture Notes in Computer Science 4051, pp.3-14, 2006.
 
Randomized Computations on Large Data Sets: Tight Lower Bounds,
with Andre Hernich and Nicole Schweikardt. In Proceedings of the 25th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'06), pp.243-252, 2006.
 
Cover  Parameterized Complexity Theory,
with Jörg Flum. Springer-Verlag, 2006.
 
Bounded fixed-parameter tractability and log2n nondeterministic bits ,
with Jörg Flum and Mark Weyer. Journal of Computer and System Sciences 72:34-71, 2006.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp.555-567, 2004. (Abstract)
 
The complexity of partition functions,
with Andrei Bulatov. Theoretical Computer Science 348:148-186, 2005.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp. 294-306, 2004. (Abstract)
 
Hypertree Decompositions: Structure, Algorithms, and Applications,
with Georg Gottlob, Nysret Musliu, Marko Samer, and Francesco Scarcello Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), Lecture Notes in Computer Science , pp.1-15, 2005. (Abstract)
 
The expressive power of two-variable least fixed-point logics,
with Stephan Kreutzer and Nicole Schweikardt. Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS'05), Lecture Notes in Computer Science , pp.422-434, 2005. (Abstract)
 
The succinctness of first-order logic on linear orders,
with Nicole Schweikardt. Logical Methods in Computer Science, 1(1), 2005.
Conference version in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp. 438-447, 2004.
 
Machine-based methods in parameterized complexity theory,
with Yijia Chen and Jörg Flum. Theoretical Computer Science., 339:167-199, 2005. (Abstract)
 
The complexity of querying external memory and streaming data,
with Christoph Koch and Nicole Schweikardt. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05), Lecture Notes in Computer Science 3623, pp.1-16, 2005. (Abstract)
 
Lower Bounds for Sorting with Few Random Accesses to External Memory,
with Nicole Schweikardt. In Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'05), pp.238-249, 2005. (Abstract)
 
Model-Checking Problems as a Basis for Parameterized Intractability,
with Jörg Flum. Logical Methods in Computer Science 1(1), 2005.
Conference version in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp.388-397, 2004.
 
The complexity of first-order and monadic second-order logic revisited,
with Markus Frick. Annals of Pure and Applied Logic 130: 3-31, 2004. (Abstract)
Conference version in Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215-224, 2002.
 
Parameterized Complexity and Subexponential Time,
with Jörg Flum. Bulletin of the European Association for Theoretical Computer Science 84, October 2004.
 
The parameterized complexity of counting problems,
with Jörg Flum. SIAM Journal on Computing 33:892-922, 2004. (Abstract)
Conference version in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), pp. 538-547, 2002.
 
An Existential Locality Theorem ,
with Stefan Wöhrle. Annals of Pure and Applied Logic, 129: 131-148, 2004. (Abstract)
Conference Version in Proceedings of the 10th Annual Conference of the European Association for Computer Science Logic (CSL'01), Lecture Notes in Computer Science 2142, pp.99-114, Springer-Verlag 2001.
 
Computing Crossing Numbers in Quadratic Time .
Journal of Computer and System Sciences, 68(2):285-302, 2004. (Abstract)
Conference version in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231-236, 2001.
 
Learnability and Definability in Trees and Similar Structures ,
with Gyorgy Turan. Theory of Computing Systems 37(1):193-220, 2004. (Abstract)
Conference version in Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02), Lecture Notes in Computer Science 2285, pp.645-658, Springer-Verlag 2002.
 
Local tree-width, excluded minors, and approximation algorithms.
Combinatorica 23(4):613-632, 2003. (Abstract)
 
Describing Parameterized Complexity Classes ,
with Jörg Flum. Information and Computation 187: 291-319, 2003. (Abstract)
Conference version in Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02), Lecture Notes in Computer Science 2285, pp.359-371, Springer-Verlag 2002.
 
Comparing the succinctness of monadic query languages over finite trees,
with Nicole Schweikardt. RAIRO - Theoretical Informatics and Applications (ITA) 38:343-373, 2004.
Conference version in Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03), Lecture Notes in Computer Science 2803, pp.226-240, 2003. (Abstract)
 
Path Queries on Compressed XML,
with Peter Buneman and Christoph Koch. In Proceedings of the 29th Conference on Very Large Data Bases (VLDB 2003), pp.141-152, 2003.
 
Query Evaluation on Compressed Trees,
with Markus Frick and Christoph Koch. Conference version in Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03), pp.188-197, 2003.
 
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory,
with Yijia Chen and Jörg Flum. In Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003. (Abstract)
 
Reachability and Connectivity Queries in Constraint Databases,
with Michael Benedikt, Leonid Libkin, and Luc Segoufin. Journal of Computer System Sciences 66(1):169-206, 2003. (Abstract)
Conference version in Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'00), 2000.
 
Parameterized Complexity for the Database Theorist,
SIGMOD Record 31(4), 2002.
 
Query evaluation via tree-decompositions ,
with Jörg Flum and Markus Frick. Journal of the ACM 49:716-752, 2002. (Abstract)
Conference version in Proceedings of the 8th International Conference on Database Theory. Lecture Notes in Computer Science 1973, Springer-Verlag, 2001.
 
On first-order topological queries ,
with Luc Segoufin. ACM Transactions on Computational Logic 3(3):336-358, 2002. (Abstract)
Conference version in Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000.
 
Large finite structures with few Lk-types.
Information and Computation 179(2): 250-278, 2002.
Conference Version in Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, 1997. ( Abstract)
 
When is the evaluation of conjunctive queries tractable ?,
with Thomas Schwentick and Luc Segoufin. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.657-666, 2001. (Abstract)
 
The Parameterized Complexity of Database Queries,
In Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.82-92, 2001. (Abstract)
 
Fixed-parameter tractability, definability, and model checking,
with Jörg Flum. SIAM Journal on Computing 31:113-145, 2001. (Abstract)
 
Generalized model-checking problems for first-order logic.
In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science 2010, pp.12-26, Springer-Verlag 2001. (Abstract)
 
Deciding first-order properties of locally tree-decomposable structures,
with Markus Frick. Journal of the ACM 48:1184-1206, 2001.
Conference version in Proceedings of the 26th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science 1644, Springer-Verlag, 1999.
 
Isomorphism testing for embeddable graphs through definability.
Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000. (Abstract)
 
Locality of order-invariant first-order formulas,
with Thomas Schwentick. ACM Transactions on Computational Logic 1:112-130, 2000.
Conference version in Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 1450, Springer-Verlag, 1998. (Abstract)
 
On fixed-point logic with counting,
with Jörg Flum. Journal of Symbolic Logic 65:777- 787, 2000.
 
Equivalence in finite-variable logics is complete for polynomial time.
Combinatorica 19:507-532, 1999.
 
Descriptive and parameterized complexity,
In Computer Science Logic, 13th Workshop (CSL'99). Lecture Notes in Computer Science 1683, Springer-Verlag, 1999. (Abstract)
 
Definability and descriptive complexity on databases of bounded tree-width,
with Julian Marino. In Proceedings of the 7th International Conference on Database Theory (ICDT'99). Lecture Notes in Computer Science 1540, Springer-Verlag, 1999. (Abstract)
 
Zur Struktur dessen, was wirklich berechenbar ist,
with Heinz-Dieter Ebbinghaus. Philosophia Naturalis 36:91-116, 1999.
 
Finite variable logics in descriptive complexity theory,
Bulletin of Symbolic Logic 4:345-398, 1998.
 
Fixed-point logics on planar graphs,
in Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998. (Abstract)
 
Canonization for Lk-equivalence is hard.
In Computer Science Logic (CSL'97), 11th Workshop, 1997. Eds. M. Nielsen, W. Thomas. Lecture Notes in Computer Science 1414, Springer Verlag 1998.  (Abstract)
 
Existential least fixed-point logic and its relatives,
in Journal of Logic and Computation 7: 205-228, 1997. (Abstract)
 
Arity hierarchies,
in Annals of Pure and Applied Logic 82: 103-163, 1996. (Abstract)
 
Some remarks on finite Löwenheim-Skolem theorems,
in Mathematical Logic Quarterly 42: 569-571, 1996. (Abstract)
 
A double arity hierarchy theorem for transitive closure logic,
with Lauri Hella. In Archive for Mathematical Logic 35:157-171, 1996. (Abstract)
 
Complete Problems for fixed-point logics,
in Journal of Symbolic Logic 60: 517-527, 1995. (Abstract)
 
Bounded-arity hierarchies in fixed-point logics,
in Computer Science Logic (CSL'93), 7th Workshop, Swansea 1993. Eds. E. Börger,Y. Gurevich, K. Meinke. Lecture Notes in Computer Science 832, Springer Verlag. (Abstract)
The Complexity of Finite-Variable Theories
Habilitationsschrift at the Albert-Ludwigs-Universität Freiburg, November 1997.
 
The Structure of Fixed-Point Logics
Dissertation at the Albert-Ludwigs-Universität Freiburg, December 1994.
 
Fixpunktlogiken in der endlichen Modelltheorie
Diplomarbeit at the Albert-Ludwigs-Universität Freiburg, April 1992.