1

H.L. Bodlaender, R.G. Downey, M.R. Fellows, M.T. Hallett, and H.T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11:49--57, 1995.

2

Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States  [doi>10.1145/800105.803397]

3

Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991

4

Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995  [doi>10.1137/S0097539792228228]

5

Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995  [doi>10.1016/0304-3975(94)00097-3]

6

R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.

7

R.G. Downey, M.R. Fellows, and U. Taylor. The parameterized complexity of relational database queries and an improved characterization of W {I}. In D.S. Bridges, C. Calude, P. Gibbons, S. Reeves, and I.H. Witten, editors, Combinatorics, Complexity, and Logic--Proceedings of DMTCS '96, pages 194--213. Springer-Verlag, 1996.

8

E. Allen Emerson , Chin-Laung Lei, Modalities for model checking: branching time logic strikes back, Science of Computer Programming, v.8 n.3, p.275-306, June 1, 1987  [doi>10.1016/0167-6423(87)90036-0]

9

Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001

10

Jörg Flum , Martin Grohe, Fixed-Parameter Tractability, Definability, and Model-Checking, SIAM Journal on Computing, v.31 n.1, p.113-145, 2001  [doi>10.1137/S0097539799360768]

11

Markus Frick, Generalized Model-Checking over Locally Tree-Decomposable Classes, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.632-644, March 14-16, 2002

12

Markus Frick , Martin Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM (JACM), v.48 n.6, p.1184-1206, November 2001  [doi>10.1145/504794.504798]

13

Markus Frick , Martin Grohe, The Complexity of First-Order and Monadic Second-Order Logic Revisited, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.215-224, July 22-25, 2002

14

Georg Gottlob , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002

15

Georg Gottlob , Francesco Scarcello , Martha Sideri, Fixed-Parameter Complexity in AI and Nonmonotonic Reasoning, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, p.1-18, December 02-04, 1999

16

Martin Grohe, The parameterized complexity of database queries, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.82-92, May 2001, Santa Barbara, California, United States  [doi>10.1145/375551.375564]

17

Orna Lichtenstein , Amir Pnueli, Checking that finite state concurrent programs satisfy their linear specification, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-107, January 14-16, 1985, New Orleans, Louisiana, United States  [doi>10.1145/318593.318622]

18

Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States  [doi>10.1145/335168.335217]

19

Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries, Journal of Computer and System Sciences, v.58 n.3, p.407-427, June 1999  [doi>10.1006/jcss.1999.1626]

20

D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6:505--526, 1996.

21

U. Stege. Resolving Conflicts in Problems from Computational Biology. PhD thesis, ETH Zuerich, 2000. PhD Thesis No. 13364.

22

L.J. Stockmeyer. The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974.

23

J.W. Thatcher and J.B. Wright. Generalised finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2:57--81, 1968.

24

Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States  [doi>10.1145/800070.802186]

25

M. Yannakakis, Perspectives on database theory, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.224, October 23-25, 1995

Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland

Leopoldo Bertossi, Consistent query answering in databases, ACM SIGMOD Record, v.35 n.2, June 2006

Georg Gottlob , Alan Nash, Efficient core computation in data exchange, Journal of the ACM (JACM), v.55 n.2, p.1-49, May 2008

Rebecca J. Cathey , Steven M. Beitzel , Eric C. Jensen , David Grossman , Ophir Frieder, Using a relational database for scalable XML search, The Journal of Supercomputing, v.44 n.2, p.146-178, May 2008

Yongmei Liu , Hector J. Levesque, A tractability result for reasoning with incomplete first-order knowledge bases, Proceedings of the 18th international joint conference on Artificial intelligence, p.83-88, August 09-15, 2003, Acapulco, Mexico

Leonid Libkin, The finite model theory toolbox of a database theoretician, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA

Martin Grohe: colleagues