Descriptive and parameterized complexity

DOI10.1007/3-540-48168-0_3MaRDI QIDQ4945215zbMATH OpenFDO

Authors Martin Grohe

Publication date 23 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48168-0_3

zbMATH Keywords

descriptive complexity theoryfinite structureparameterized complexitysurvey

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 4106276
• scientific article; zbMATH DE number 17544
• Describing parameterized complexity classes
• scientific article; zbMATH DE number 2086399
• Descriptive complexity, lower bounds and linear time
• Descriptive characterizations of computational complexity
• Parameterized complexity
• Descriptive complexity of \(\#\)P functions
• Descriptive complexity of \#P functions: a new perspective
• Descriptive complexity of deterministic polylogarithmic time

Cited in

(26)

• A descriptive complexity approach to the linear hierarchy.
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• Describing parameterized complexity classes
• The parameterized complexity and kernelization of resilience for database queries
• Descriptive complexity of \#P functions: a new perspective
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Descriptive complexity of deterministic polylogarithmic time
• A linear-time kernelization for the rooted k-leaf outbranching problem
• A general purpose algorithm for counting simple cycles and simple paths of any length
• Experimental descriptive complexity
• Structure and specification as sources of complexity
• Parameterized complexity of fixed variable logics
• The parameterized complexity of relational database queries and an improved characterization of \(W[1]\)
• Computation Models for Parameterized Complexity
• scientific article; zbMATH DE number 1499087 (Why is no real title available?)
• scientific article; zbMATH DE number 1508265 (Why is no real title available?)
• The ring grooming problem
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• scientific article; zbMATH DE number 2086399 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• On the descriptive complexity of color coding
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• On the complexity of Gödel's proof predicate
• An analysis of the W*-hierarchy
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough
• Parameterized Complexity of DPLL Search Procedures

This page was built for publication: Descriptive and parameterized complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945215)