Logic and
Theory of
Discrete Systems
Informatik 7
Martin Grohe's Publications
 WeisfeilerLeman Meets Homomorphisms,
 with Holger Dell, Martin Grohe, Gaurav Rattan. Conference Version to appear in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
 An improved isomorphism test for boundedtreewidth graphs,
 with Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. Conference Version to appear in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
 Definable Decompositions for Graphs of Bounded Linear Clique Width,
 with Mikolaj Bojanczyk and Michal Pilipczuk. Conference Version to appear in Proceedings of the 33rd ACMIEEE Symposium on Logic in Computer Science, 2018
 FirstOrder Query Evaluation with Cardinality Conditions,
 with Nicole Schweikardt. Conference Version to appear in Proceedings of the 37th ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2018
 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.
 Learning MSODefinable Hypotheses on Strings,
 with Christof Löding and Martin Ritzert. Conference version in Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017.
 Descriptive Complexity, Canonisation, and Definable Graph Structure Theory,
 Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017.
 Preliminary draft, 2013.
 The Hardness of Embedding Grids and Walls,
 with Yijia Chen and BingKai Lin. Conference version in Proceedings of the 43rd International Workshop on GraphTheoretic Concepts in Computer Science, 2017.
 Learning firstorder definable concepts over structures of small degree,
 with Martin Ritzert. Conference version in Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017.
 Descriptive Complexity of Solving Linear Equation Systems and its Applications,
 with Wied Pakusa. In Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017.
 Decding FirstOrder properties of Nowhere Dense Graphs
 with Stephan Kreutzer and Sebastian Siebertz. Journal of the ACM 64(3). Conference version in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC'14), pp.8998, 2014.
 Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement ,
 with Paul Bonsma and Christoph Berkholz. Theory of Computing Systems 60(4):581614, 2017. 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.145156, 2013.
 Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
 with Christoph Berkholz. Conference Version in Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, pp.327339, 2017.
 Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles).
 CoRR abs/1605.06704, 2016.
 Quasi4Connected 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.397406, 2016.
 Computing with Tangles
 with Pascal Schweitzer. In SIAM Journal on Discrete Mathematics, 30(2):12131247, 2016. Conference Version in Proceedings of the 47th ACM Symposium on Theory of Computing (STOC'15), pp.683692, 2015.
 Where FirstOrder and Monadic SecondOrder Logic Coincide,
 with Michael Elberfeld and Till Tantau. In ACM Transactions on Computational Logic, 17(4):25:125:18, 2016. Conference version in Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS 2016, pp.265274, 2012.
 Tangles and Connectivity in Graphs
 In A.H. Dediu and J. Janousek and C. MartinVide 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.2442, 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 GraphTheoretic Concepts in Computer Science (WG'15), Lecture Notes in Computer Science 9224, pp.325338, 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.10101029, 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.193209, 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.155166, 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):114159, 2015. Conference version in Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pp.173192, 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 ACMSIAM Symposium on Discrete Algorithms (SODA 2006), pp.289298, 2006.
 Choiceless Polynomial Time on Structures with Small Abelian Colour Classes,
 with Faried Abu Zaid, Erich Grädel, and Wied Pakusa. In E. CsuhajVarjú 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.5062, 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.
 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.1622, 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):17371767, 2013. Conference version in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739748, 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.2140, 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.321338, 2013.

 A Simple Algorithm for the Graph Minor Decomposition — Logic Meets Structural Graph Theory —
 with Kenichi Kawarabayashi and Bruce Reed. In Proceedings of the of the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2013), pp.414431, 2013.

 FixedPoint 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:638650, 2012. Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.231242, 2009.

 LRecursion 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.

 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):104112, 2011.

 Finding Topological Subgraphs is FixedParameter Tractable,
 with Dániel Marx, KenIch Kawarbayashi, and Paul Wollan. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pp.479488, 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.275289, 2010.

 FixedPoint 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.328353, 2010.

 A complexity dichotomy for partition functions with mixed signs,
 with Leslie Ann Goldberg, Mark Jerrum, and Marc Thurley. SIAM Journal on Computing 39:336402, 2010.
Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.493504, 2009.

 Constraint satisfaction problems with succinctly specified relations,
 with Hubie Chen. Journal of Computer and System Sciences 76(8):847860, 2010.

 FixedPoint Definability and Polynomial Time.
 In Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.2023, 2009. Slides of my CSLtalk.

 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.113122, 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:533560, 2009.
Conference version in In Proceedings of the 11th International Conference on Database Theory (ICDT'07), Lecture Notes in Computer Science 4353, pp.284298, 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:218228, 2009.

 Preservation under Extensions on WellBehaved Finite Structures,
 with Albert Atserias and Anuj Dawar. SIAM Journal on Computing, 38:13641381, 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.14371450, 2005. (Abstract)

 Nondichotomies 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.184196, 2008.

 Definable tree decompositions.
 In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406417, 2008.

 The quest for a logic capturing PTIME.
 In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267271, 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.818, 2008.

 Computing excluded minors,
 with Isolde Adler and Stephan Kreutzer. In Proceedings of the of the 19th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2008), pp.641650, 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:12281258, 2007. Conference version in Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314328, 2006.

 Bounded FixedParameter Tractability and Reducibility,
 with Rod Downey, Jörg Flum, and Mark Weyer. Annals of Pure and Applied Logic 148:119, 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.363374, 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.913924, 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.270279, 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.552561, 2003. (Abstract)

 HypertreeWidth and Related Hypergraph Invariants,
 with Isolde Adler and Georg Gottlob. European Journal of Combinatorics, 28:21672181, 2007.
Conference version in Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05), DMTCS Proceedings Series, Volume AE, pp.510, 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:199217, 2007. Conference version in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp.10761088, 2005. (Abstract)

 An analysis of the W*hierarchy,
 with Yijia Chen and Jörg Flum. Journal of Symbolic Logic 72:513534, 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.109120, 2006.

 Approximation Schemes for FirstOrder Definable Optimisation Problems ,
 with Anuj Dawar, Stephan Kreutzer, and Nicole Schweikardt. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411420, 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.5872, 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.314, 2006.

 Randomized Computations on Large Data Sets: Tight Lower Bounds,
 with Andre Hernich and Nicole Schweikardt. In Proceedings of the 25th ACM SigactSigart Symposium on Principles of Database Systems (PODS'06), pp.243252, 2006.

 Parameterized Complexity Theory,
 with Jörg Flum. SpringerVerlag, 2006.

 Bounded fixedparameter tractability and log^{2}n nondeterministic bits ,
 with Jörg Flum and Mark Weyer. Journal of Computer and System Sciences 72:3471, 2006.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp.555567, 2004. (Abstract)

 The complexity of partition functions,
 with Andrei Bulatov. Theoretical Computer Science 348:148186, 2005.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp. 294306, 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 GraphTheoretic Concepts in Computer Science (WG'05), Lecture Notes in Computer Science , pp.115, 2005. (Abstract)

 The expressive power of twovariable least fixedpoint 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.422434, 2005. (Abstract)

 The succinctness of firstorder 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. 438447, 2004.

 Machinebased methods in parameterized complexity theory,
 with Yijia Chen and Jörg Flum. Theoretical Computer Science., 339:167199, 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.116, 2005. (Abstract)

 Lower Bounds for Sorting with Few Random Accesses to External Memory,
 with Nicole Schweikardt. In Proceedings of the 24th ACM SigactSigart Symposium on Principles of Database Systems (PODS'05), pp.238249, 2005. (Abstract)

 ModelChecking 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.388397, 2004.

 The complexity of firstorder and monadic secondorder logic revisited,
 with Markus Frick. Annals of Pure and Applied Logic 130: 331, 2004. (Abstract)
Conference version in Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215224, 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:892922, 2004. (Abstract)
Conference version in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), pp. 538547, 2002.

 An Existential Locality Theorem ,
 with Stefan Wöhrle. Annals of Pure and Applied Logic, 129: 131148, 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.99114, SpringerVerlag 2001.

 Computing Crossing Numbers in Quadratic Time .
 Journal of Computer and System Sciences, 68(2):285302, 2004. (Abstract)
Conference version in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231236, 2001.

 Learnability and Definability in Trees and Similar Structures ,
 with Gyorgy Turan. Theory of Computing Systems 37(1):193220, 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.645658, SpringerVerlag 2002.

 Local treewidth, excluded minors, and approximation algorithms.
 Combinatorica 23(4):613632, 2003. (Abstract)

 Describing Parameterized Complexity Classes ,
 with Jörg Flum. Information and Computation 187: 291319, 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.359371, SpringerVerlag 2002.

 Comparing the succinctness of monadic query languages over finite trees,
 with Nicole Schweikardt. RAIRO  Theoretical Informatics and Applications (ITA) 38:343373, 2004.
Conference version in Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03), Lecture Notes in Computer Science 2803, pp.226240, 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.141152, 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.188197, 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.1329, 2003. (Abstract)

 Reachability and Connectivity Queries in Constraint Databases,
 with Michael Benedikt, Leonid Libkin, and Luc Segoufin. Journal of Computer System Sciences 66(1):169206, 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 treedecompositions ,
 with Jörg Flum and Markus Frick. Journal of the ACM 49:716752, 2002. (Abstract)
Conference version in Proceedings of the 8th International Conference on Database Theory. Lecture Notes in Computer Science 1973, SpringerVerlag, 2001.

 On firstorder topological queries ,
 with Luc Segoufin. ACM Transactions on Computational Logic 3(3):336358, 2002. (Abstract)
Conference version in Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000.

 Large finite structures with few L^{k}types.
 Information and Computation 179(2): 250278, 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.657666, 2001. (Abstract)

 The Parameterized Complexity of Database Queries,
 In Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.8292, 2001. (Abstract)

 Fixedparameter tractability, definability, and model checking,
 with Jörg Flum. SIAM Journal on Computing 31:113145, 2001. (Abstract)

 Generalized modelchecking problems for firstorder logic.
 In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science 2010, pp.1226, SpringerVerlag 2001. (Abstract)

 Deciding firstorder properties of locally treedecomposable structures,
 with Markus Frick. Journal of the ACM 48:11841206, 2001.
Conference version in Proceedings of the 26th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science 1644, SpringerVerlag, 1999.

 Isomorphism testing for embeddable graphs through definability.
 Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000. (Abstract)

 Locality of orderinvariant firstorder formulas,
 with Thomas Schwentick. ACM Transactions on Computational Logic 1:112130, 2000.
Conference version in Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 1450, SpringerVerlag, 1998. (Abstract)

 On fixedpoint logic with counting,
 with Jörg Flum. Journal of Symbolic Logic 65:777 787, 2000.

 Equivalence in finitevariable logics is complete for polynomial time.
 Combinatorica 19:507532, 1999.

 Descriptive and parameterized complexity,
 In Computer Science Logic, 13th Workshop (CSL'99). Lecture Notes in Computer Science 1683, SpringerVerlag, 1999. (Abstract)

 Definability and descriptive complexity on databases of bounded treewidth,
 with Julian Marino. In Proceedings of the 7th International Conference on Database Theory (ICDT'99). Lecture Notes in Computer Science 1540, SpringerVerlag, 1999. (Abstract)

 Zur Struktur dessen, was wirklich berechenbar ist,
 with HeinzDieter Ebbinghaus. Philosophia Naturalis 36:91116, 1999.

 Finite variable logics in descriptive complexity theory,
 Bulletin of Symbolic Logic 4:345398, 1998.

 Fixedpoint logics on planar graphs,
 in Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998. (Abstract)

 Canonization for L^{k}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 fixedpoint logic and its relatives,
 in Journal of Logic and Computation 7: 205228, 1997. (Abstract)

 Arity hierarchies,
 in Annals of Pure and Applied Logic 82: 103163, 1996. (Abstract)

 Some remarks on finite LöwenheimSkolem theorems,
 in Mathematical Logic Quarterly 42: 569571, 1996. (Abstract)

 A double arity hierarchy theorem for transitive closure logic,
 with Lauri Hella. In Archive for Mathematical Logic 35:157171, 1996. (Abstract)

 Complete Problems for fixedpoint logics,
 in Journal of Symbolic Logic 60: 517527, 1995. (Abstract)

 Boundedarity hierarchies in fixedpoint 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 FiniteVariable Theories
 Habilitationsschrift at the AlbertLudwigsUniversität Freiburg, November 1997.

 The Structure of FixedPoint Logics
 Dissertation at the AlbertLudwigsUniversität Freiburg, December 1994.

 Fixpunktlogiken in der endlichen Modelltheorie
 Diplomarbeit at the AlbertLudwigsUniversität Freiburg, April 1992.
Datenschutzerklaerung