Parameterized complexity for the database theorist
ACM SIGMOD RecordPublished 1 December 2002
Martin Grohe
Citations58
SJR quartileQ2
SJR score0.69
SNIP0.92
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This short paper is a gentle introduction to the theory of parameterized complexity theory, focusing on the results most relevant for database theory.
Abstract
article Parameterized complexity for the database theorist Share on Author: Martin Grohe University of Edinburgh, Edinburgh, Scotland, UK University of Edinburgh, Edinburgh, Scotland, UKView Profile Authors Info & Claims ACM SIGMOD RecordVolume 31Issue 4December 2002 pp 86–96https://doi.org/10.1145/637411.637428Online:01 December 2002Publication History 30citation306DownloadsMetricsTotal Citations30Total Downloads306Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
Computer Science
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Electronic Notes in Theoretical Computer ScienceParameterized Complexity
2,884 Citations2002Michael R. Fellows
Optimal implementation of conjunctive queries in relational data bases
1,237 Citations1977Ashok K. Chandra, Philip M. Merlin
It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal.
The complexity of relational query languages (Extended Abstract)
1,189 Citations1982Moshe Y. Vardi
The pattern which will be shown is that the expression complexity of the investigated languages is one exponential higher then their data complexity, and for both types of complexity the authors show completeness in some complexity class.
Theory of Computing SystemsGeneralized finite automata theory with an application to a decision problem of second-order logic
737 Citations1968J. W. Thatcher, Jesse B. Wright
The standard closure theorems are proved for the class of sets “recognizable” by finite algebras, and a generalization of Kleene's regularity theory is presented.
Checking that finite state concurrent programs satisfy their linear specification
618 Citations1985Orna Lichtenstein, Amir Pnueli
An algorithm for checking satisfiability of a linear time temporal logic formula over a finite state concurrent program and a formal proof in case the formula is valid over the program is presented.
Theoretical Computer ScienceFixed-parameter tractability and completeness II: On completeness for W[1]
587 Citations1995Rod Downey, Michael R. Fellows
This work shows that INDEPENDENT SET is complete for W, and the W Hierarchy of parameterized problems was defined, and complete problems were identified for the classes W [ t ] for t ⩾ 2.
SIAM Journal on ComputingFixed-Parameter Tractability and Completeness I: Basic Results
462 Citations1995Rod Downey, Michael R. Fellows
Elsevier eBooksGraph Rewriting: An Algebraic and Logic Approach
356 Citations1990B. Courcelle
This chapter presents three mathematical tools that can be used to describe graph-grammars and the sets generated by them, and presents the use of category theory for specifying graph rewriting rules in a precise and concise way.
Science of Computer ProgrammingModalities for model checking: branching time logic strikes back
327 Citations1987E. Allen Emerson, Chin‐Laung Lei
This paper presents a unified approach for efficient model checking under a broad class of generalized fairness constraints in a branching time framework extending that of Clarke et al. (1983), and argues that branching time logic is always better than linear time logic for model checking.
Journal of the ACMDeciding first-order properties of locally tree-decomposable structures
229 Citations2001Markus Frick, Martin Grohe
It is shown that for each property φ of structures that is definable in first-order logic and for each locally tree-decomposable class C of structures, there is a linear time algorithm deciding whether a given structure A ∈ C hasproperty φ.
Mathematical Structures in Computer ScienceLinear time computable problems and first-order descriptions
153 Citations1996Detlef Seese
Using an old technique of Hanf and other techniques developed to prove the decidability of formal theories in mathematical logic, it is shown that an arbitrary FO-problem over relational structures of bounded degree can be solved in linear time.
SIAM Journal on ComputingFixed-Parameter Tractability, Definability, and Model-Checking
115 Citations2001Jörg Flum, Martin Grohe
This article proves an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations, and gives a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic.
Computer applications in the biosciencesParameterized complexity analysis in computational biology
108 Citations1995Hans L. Bodlaender, Rodney G. Downey +3 more
It is argued that for many problems in this setting, parameterized computational complexity rather than NP-completeness is the appropriate tool for studying apparent intractability and a new result is described for the Longest Common Subsequence problem.
Monadic queries over tree-structured data
103 Citations2003Georg Gottlob, Christoph Koch
A number of new results related to the complexity of such languages over so-called axis relations (such as "child" or "descendant") which are motivated by their presence in the XPath standard or by their utility for data extraction (wrapping) are provided.
The complexity of first-order and monadic second-order logic revisited
62 Citations2003Markus Frick, Martin Grohe
Expressive and efficient pattern languages for tree-structured data (extended abstract)
60 Citations2000Frank Neven, Thomas Schwentick
It would be desirable to have a query language for tree-structured data that is as easily usable as SQL, as expressive as monadic second-order logic (MSO), and efficiently evaluable.
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1].
57 Citations1996Rodney G. Downey, Michael R. Fellows +1 more
The parameterized complexity of database queries
40 Citations2001Martin Grohe
The main results presented here classify the evaluation of first-order queries and conjunctive queries as hard parameterized problems.
Lecture notes in computer scienceQuery Evaluation via Tree-Decompositions
39 Citations2001Jörg Flum, Markus Frick +1 more
Perspectives on database theory
26 Citations2002Mihalis Yannakakis
A flavor of the types of problems that database theory addresses is given, and how research in the area has evolved over the years is reviewed, to point to some topics that may be of interest to the FOCS community tempted to work in database theory.
Lecture notes in computer scienceFixed-Parameter Complexity in AI and Nonmonotonic Reasoning
24 Citations1999Georg Gottlob, Francesco Scarcello +1 more
Lecture notes in computer scienceGeneralized Model-Checking over Locally Tree-Decomposable Classes
5 Citations2002Markus Frick
It is proved that construction, listing, and counting problems definable in first-order logic can be solved in linear time on locally tree-decomposable classes of structures.