Parameterized Complexity Classes under Logical Reductions

DOI10.1007/978-3-642-03816-7_23zbMath1250.68115OpenAlexW1881947656WikidataQ58215569 ScholiaQ58215569MaRDI QIDQ3182930

Anuj Dawar, Yuguo He

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_23

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Elements of finite model theory.
• Describing parameterized complexity classes
• Parametrized complexity theory.
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Relational queries computable in polynomial time
• Some Remarks on Generalized Spectra
• Computer Science Logic

This page was built for publication: Parameterized Complexity Classes under Logical Reductions