Person
Dr. rer. nat., UniversitätsprofessorMartin Grohe
Address
Building: E1, 1. Etage
Room: 4116a
Ahornstraße 55
52074 Aachen
Contact
- workPhone
- Phone: +49 241 80 21700
Office Hours
- Montag, 15:00 - 16:00 Uhr
Research Interests
Logic, algorithms und complexity, database theory, graph theory, algorithmic learning theory
Books
| Title | Author(s) | Published |
|---|---|---|
|
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory |
Martin Grohe |
Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017 |
| Model Theoretic Methods in Finite Combinatorics | Martin Grohe, Janos Makowsky (Ed.) | Contemporary Mathematics 558, American Mathematical Society, 2011 |
| Martin Grohe, Jörg Flum | Springer-Verlag, 2006 |
Publications
| Title | Author(s) | Published in |
|---|---|---|
| A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus | Martin Grohe, Sandra Kiefer | CoRR abs/1904.07216 (2019) |
|
Canonisation and Definability for Graphs of Bounded Rank Width |
Martin Grohe, Daniel Neuen |
CoRR abs/1901.10330 (2019) |
|
Weisfeiler and Leman go neural: Higher-order graph neural networks |
Chistopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe | Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. To appear. |
|
Probabilistic databases with an infinite open-world assumption |
Martin Grohe, Peter Lindner | Proceedings of the 38th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2019. To appear |
| Martin Grohe, Daniel Neuen, Pascal Schweitzer | Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, pages 89–100, 2018 | |
| Martin Grohe, Gaurav Rattan, Gerhard Woeginger | In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018 | |
| Holger Dell, Martin Grohe, Gaurav Rattan | Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018 | |
| Martin, Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking |
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018 |
|
|
Definable Decompositions for Graphs of Bounded Linear Clique Width |
Martin Grohe, Mikolaj Bojanczyk, Michal Pilipczuk | Proceedings of the 33rd ACM-IEEE Symposium on Logic in Computer Science, 2018 |
| First-Order Query Evaluation with Cardinality Conditions | Martin Grohe, Nicole Schweikardt | Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2018 |
| Color Refinement and its Applications | Martin Grohe, Kristian Kersting, Martin Mladenov, Pascal Schweitzer |
Preliminary Draft of a Chapter, 2017 Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, David Poole, An Introduction to Lifted Probabilistic Inference, Cambridge University Press |
| Learning MSO-Definable Hypotheses on Strings | Martin Grohe, Christof Löding, Martin Ritzert | Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017 |
|
Martin Grohe, Yijia Chen, BingKai Lin |
Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, 2017 | |
|
Learning first-order definable concepts over structures of small degree |
Martin Grohe, Martin Ritzert |
Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017 |
| Descriptive Complexity of Solving Linear Equation Systems and its Applications |
Martin Grohe, Wied Pakusa |
Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017 |
| Deciding First-Order properties of Nowhere Dense Graphs | Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
Journal of the ACM 64(3) 2017 Proceedings of the 46th ACM Symposium on Theory of Computing (STOC'14), pp.89-98, 2014 |
|
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement |
Martin Grohe, Paul Bonsma, Christoph Berkholz |
Theory of Computing Systems 60(4):581-614, 2017 Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013) |
| Linear Diophantine Equations, Group CSPs, and Graph Isomorphism | Martin Grohe, Christoph Berkholz | 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) | Martin Grohe | CoRR abs/1605.06704, 2016 |
| Quasi-4-Connected Components | Martin Grohe |
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, 2016 |
| Martin Grohe, Michael Elberfeld, Marlin Frickenschmidt | Proceedings of the 31st IEEE Symposium on Logic in Computer Science (LICS 2016), pp.397-406, 2016 | |
| Martin Grohe, Pascal Schweitzer |
SIAM Journal on Discrete Mathematics, 30(2):1213-1247, 2016 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 | Martin Grohe, Michael Elberfeld, Till Tantau |
ACM Transactions on Computational Logic, 17(4):25:1-25:18, 2016 Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS 2016, pp.265-274, 2012 |
| Martin Grohe |
Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016) |
|
| Martin grohe, S. Kreutzer and R. Rabinovich and S. Siebertz, K. Stavropoulos |
Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'15) |
|
| Isomorphism Testing for Graphs of Bounded Rank Width | Martin Grohe, Pascal Schweitzer | Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS15), pp.1010-1029, 2015 |
| Martin Grohe, Erich Grädel |
Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday |
|
|
Limitations of Algebraic Approaches to Graph Isomorphism Testing |
Martin Grohe, Christoph Berkholz |
Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), Part II |
| Martin Grohe | Encyclopedia of Applied and Computational Mathematics, Springer Verlag, 2015 | |
| Pebble Games and Linear Equations | Martin Grohe, Martin Otto |
Journal of Symbolic Logic 80(3), 2015 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 |
Martin Grohe, Dániel Marx |
SIAM Journal on Computing 44(1):114-159, 2015 Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pp.173-192, 2012 |
| Constraint Solving via Fractional Edge Covers | Martin grohe, Dániel Marx |
ACM Transactions on Algorithms 11(1), 2014 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 |
Martin Grohe, Faried Abu Zaid, Erich Grädel, Wied Pakusa |
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Part I |
| Martin Grohe, Kristian Kersting and Martin Mladenov, Erkal Selman |
Proceedings of the 22nd Annual European Symposium on Algorithms |
|
| Power Iterated Color Refinement | Martin grohe, Kristian Kersting, Martin Mladenov, Roman Garnett | Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp. 1904–1910, 2014 |
| Martin Grohe |
Proceedings of the 9th International Computer Science Symposium in Russia (CSR'14) |
|
|
Monadic Datalog Containment on Trees
|
Martin Grohe, André Frochaux, Nicole Schweikardt |
SIAM Journal on Computing 42(4):1737-1767, 2013 Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008 |
| Size bounds and query plans for relational joins | Martin Grohe, Albert Atserias and Dániel Marx |
SIAM Journal on Computing 42(4):1737-1767, 2013 Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008 |
| Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
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 |
|
| Martin Grohe |
In Search of Elegance in the Theory and Practice of Computation, Essays Dedicated to Peter Buneman |
|
| A Simple Algorithm for the Graph Minor Decomposition — Logic Meets Structural Graph Theory — | Martin Grohe, Ken-ichi Kawarabayashi, Bruce Reed | 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 | Martin Grohe |
Journal of the ACM 59(5), 2012 Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10), 2010 |
| Enumerating Homomorphisms | Martin Grohe, Andrei A. Bulatov, Victor Dalmau, Dániel Marx |
Journal of Computer and System Sciences 78:638-650, 2012 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 | Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner |
Logical Methods in Computer Science 9(1), 2012 Proceedings of the 25th International Workshop on Computer Science Logic (CSL'11) Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, 2011 |
| Methods for Algorithmic Meta Theorems | Martin Grohe, Stephan Kreutzer | Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011 |
| Counting Homomorphisms and Partition Functions | Martin Grohe, Marc Thurley | Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011 |
| From Polynomial Time Queries to Graph Structure Theory | Martin Grohe | Communications of the ACM 54(6):104-112, 2011 |
| Finding Topological Subgraphs is Fixed-Parameter Tractable | Martin Grohe, Dániel Marx, Ken-Ich Kawarbayashi, Paul Wollan | Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pp.479-488, 2011 |
| Randomisation and Derandomisation in Descriptive Complexity Theory |
Martin Grohe, Kord Eickmeyer |
Logical Methods in Computer Science, Volume 7, Issue 3, 2011 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 |
Martin Grohe |
Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday |
| A complexity dichotomy for partition functions with mixed signs | Martin Grohe, Leslie Ann Goldberg, Mark Jerrum, Marc Thurley |
SIAM Journal on Computing 39:336-402, 2010 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 | Martin Grohe, Hubie Chen | Journal of Computer and System Sciences 76(8):847-860, 2010 |
| Martin Grohe | Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.20-23, 2009 | |
| Logics with Rank Operators | Martin Grohe, Anuj Dawar, Bjarki Holm, Bastian Laubner | 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 | Martin Grohe, Andre Hernich, Nicole Schweikardt |
Journal of the ACM, 56(3), 2009 Full version of PODS'05 and PODS'06 papers |
| Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, Jan Van den Bussche |
Theory of Computing Systems, 44:533-560, 2009 Proceedings of the 11th International Conference on Database Theory (ICDT'07) |
|
| The Complexity of Datalog on Linear Orders | Martin Grohe, Götz Schwandtner | Logical Methods in Computer Science, 5(1), 2009 |
| On tree width, bramble size, and expansion | Martin Grohe, Dániel Marx | Journal of Combinatorial Theory, Series B 99:218-228, 2009 |
|
Preservation under Extensions on Well-Behaved Finite Structures |
Martin Grohe, Albert Atserias, Anuj Dawar |
SIAM Journal on Computing, 38:1364-1381, 2008 Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05) |
| Martin Grohe, Manuel Bodirsky |
roceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track B) |
|
| Definable tree decompositions | Martin Grohe | Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008 |
| The quest for a logic capturing PTIME | Martin Grohe | 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 | Martin Grohe, Kord Eickmeyer, Magdalena Grüber | Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008 |
| Computing excluded minors | Martin grohe, Isolde Adler, Stephan Kreutzer | Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.641-650, 2008 |
| Logic, graphs, and algorithms | Martin Grohe, | Logic and Automata – History and Perspectives, Amsterdam University Press, 2007 |
| An Isomorphism between Subexponential and Parameterized Complexity Theory | Martin Grohe, Yijia Chen |
SIAM Journal on Computing 37:1228-1258, 2007 Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006 |
| Bounded Fixed-Parameter Tractability and Reducibility | Martin Grohe, Rod Downey, Jörg Flum, Mark Weyer | Annals of Pure and Applied Logic 148:1-19, 2007 |
| Martin Grohe, Magdalena Grüber |
Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A) |
|
| Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt |
Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track B) |
|
| Locally Excluding a Minor | Martin Grohe, Anuj Dawar, Stephan Kreutzer | 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 |
Martin Grohe |
Journal of the ACM, 54(1), 2007 Proceedings of the 44th IEEE Symposium on Foundations of Comupter Science (FOCS'03), pp.552-561, 2003 |
| Martin Grohe, Isolde Adler and Georg Gottlob |
European Journal of Combinatorics, 28:2167-2181, 2007 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 |
Martin Grohe, Christoph Koch, Nicole Schweikardt |
Theoretical Computer Science 380:199-217, 2007 Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05) |
| An analysis of the W*-hierarchy | Martin Grohe, Yijia Chen, Jörg Flum | Journal of Symbolic Logic 72:513-534, 2007 |
| Martin Grohe, Yijia Chen, Magdalena Grüber |
Proceedings of the 2nd International Workshop on Parameterized and Exact Computation |
|
| Approximation Schemes for First-Order Definable Optimisation Problems | Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt | Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411-420, 2006 |
| Martin Grohe |
roceedings of the 31st Symposium on Mathematical Foundations of Computer Science |
|
| Martin Grohe, Oleg Verbitzky |
Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I |
|
| Randomized Computations on Large Data Sets: Tight Lower Bounds | Martin Grohe, Andre Hernich, Nicole Schweikardt | Proceedings of the 25th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'06), pp.243-252, 2006 |
|
Bounded fixed-parameter tractability and log2n nondeterministic bits |
Martin Grohe, örg Flum, Mark Weyer |
Journal of Computer and System Sciences 72:34-71, 2006 Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) |
| Martin Grohe, Andrei Bulatov |
Theoretical Computer Science 348:148-186, 2005 Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) |
|
|
Hypertree Decompositions: Structure, Algorithms, and Applications |
Martin Grohe, Georg Gottlob, Nysret Musliu, Marko Samer, Francesco Scarcello |
Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05) |
|
The expressive power of two-variable least fixed-point logics |
Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS'05) |
| The succinctness of first-order logic on linear orders | Martin Grohe, Nicole Schweikardt |
Logical Methods in Computer Science, 1(1), 2005 Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp. 438-447, 2004 |
|
Martin Grohe, Yijia Chen, Jörg Flum |
Theoretical Computer Science., 339:167-199, 2005 | |
|
The complexity of querying external memory and streaming data |
Martin Grohe, Christoph Koch, Nicole Schweikardt |
Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05) |
|
Lower Bounds for Sorting with Few Random Accesses to External Memory |
Martin Grohe, Nicole Schweikardt | Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'05), pp.238-249, 2005 |
| Model-Checking Problems as a Basis for Parameterized Intractability | Martin Grohe, Jörg Flum |
Logical Methods in Computer Science 1(1), 2005 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 |
Martin Grohe, Markus Frick |
Annals of Pure and Applied Logic 130: 3-31, 2004 Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215-224, 2002 |
| Parameterized Complexity and Subexponential Time | Martin Grohe, Jörg Flum | Bulletin of the European Association for Theoretical Computer Science 84, October 2004 |
| Martin Grohe, Jörg Flum |
SIAM Journal on Computing 33:892-922, 2004 Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), pp. 538-547, 2002 |
|
| Martin Grohe, Stefan Wöhrle |
Annals of Pure and Applied Logic, 129: 131-148, 2004 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 |
|
| Martin Grohe |
Journal of Computer and System Sciences, 68(2):285-302, 2004 Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231-236, 2001 |
|
|
Learnability and Definability in Trees and Similar Structures |
Martin Grohe, Gyorgy Turan |
Theory of Computing Systems 37(1):193-220, 2004 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 |
Martin Grohe | Combinatorica 23(4):613-632, 2003 |
| Martin Grohe, Jörg Flum |
Information and Computation 187: 291-319, 2003 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 |
Martin Grohe, Nicole Schweikardt |
RAIRO - Theoretical Informatics and Applications (ITA) 38:343-373, 2004 Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03) |
| Path Queries on Compressed XML | Martin Grohe, Peter Buneman, Christoph Koch | Proceedings of the 29th Conference on Very Large Data Bases (VLDB 2003), pp.141-152, 2003 |
| Query Evaluation on Compressed Trees | Martin Grohe, Markus Frick, 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 |
Martin Grohe, Yijia Chen, Jörg Flum | Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003 |
|
Reachability and Connectivity Queries in Constraint Databases |
Martin Grohe, Michael Benedikt, Leonid Libkin, Luc Segoufin |
Journal of Computer System Sciences 66(1):169-206, 2003 Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'00), 2000 |
| Parameterized Complexity for the Database Theorist | Martin Grohe | SIGMOD Record 31(4), 2002 |
| Martin Grohe, Jörg Flum, Markus Frick |
Journal of the ACM 49:716-752, 2002 Proceedings of the 8th International Conference on Database Theory Lecture Notes in Computer Science 1973, Springer-Verlag, 2001 |
|
| Martin Grohe, Luc Segoufin |
ACM Transactions on Computational Logic 3(3):336-358, 2002 Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000 |
|
| Martin Grohe |
Information and Computation 179(2): 250-278, 2002 Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, 1997 |
|
| Martin Grohe, Thomas Schwentick, Luc Segoufin | Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.657-666, 2001 | |
| Martin Grohe | Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.82-92, 2001 | |
|
Fixed-parameter tractability, definability, and model checking |
Martin Grohe, Jörg Flum | SIAM Journal on Computing 31:113-145, 2001 |
| Martin Grohe |
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 |
|
|
Deciding first-order properties of locally tree-decomposable structures |
Martin Grohe, Markus Frick |
Journal of the ACM 48:1184-1206, 2001 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 |
Martin Grohe | Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000 |
| Martin Grohe, Thomas Schwentick |
ACM Transactions on Computational Logic 1:112-130, 2000 Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science Lecture Notes in Computer Science 1450, Springer-Verlag, 1998 |
|
| On fixed-point logic with counting | Martin Grohe, Jörg Flum |
Journal of Symbolic Logic 65:777- 787, 2000 |
| Equivalence in finite-variable logics is complete for polynomial time | Martin Grohe | Combinatorica 19:507-532, 1999 |
| Martin Grohe |
Computer Science Logic, 13th Workshop (CSL'99) Lecture Notes in Computer Science 1683, Springer-Verlag, 1999 |
|
|
Definability and descriptive complexity on databases of bounded tree-width |
Martin Grohe, Julian Marino |
Proceedings of the 7th International Conference on Database Theory (ICDT'99) Lecture Notes in Computer Science 1540, Springer-Verlag, 1999 |
| Zur Struktur dessen, was wirklich berechenbar ist | Martin Grohe, Heinz-Dieter Ebbinghaus | Philosophia Naturalis 36:91-116, 1999 |
| Finite variable logics in descriptive complexity theory | Martin Grohe |
Bulletin of Symbolic Logic 4:345-398, 1998 |
| Martin Grohe | Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998 | |
| Martin Grohe |
Computer Science Logic (CSL'97), 11th Workshop, 1997 Lecture Notes in Computer Science 1414, Springer Verlag 1998 |
|
| Martin Grohe | Journal of Logic and Computation 7: 205-228, 1997 | |
| Martin Grohe | Annals of Pure and Applied Logic 82: 103-163, 1996 | |
| Martin Grohe | Mathematical Logic Quarterly 42: 569-571, 1996 | |
|
A double arity hierarchy theorem for transitive closure logic |
Martin Grohe, Lauri Hella | Archive for Mathematical Logic 35:157-171, 1996 |
| Martin Grohe | Journal of Symbolic Logic 60: 517-527, 1995 | |
| Martin Grohe |
Computer Science Logic (CSL'93), 7th Workshop, Swansea 1993 |
|
| The Complexity of Finite-Variable Theories | Martin Grohe | Habilitationsschrift at the Albert-Ludwigs-Universität Freiburg, November 1997 |
| The Structure of Fixed-Point Logics | Martin Grohe | Dissertation at the Albert-Ludwigs-Universität Freiburg, December 1994 |
| Fixpunktlogiken in der endlichen Modelltheorie | Martin Grohe | Diplomarbeit at the Albert-Ludwigs-Universität Freiburg, April 1992 |