First-Order Model Checking Problems Parameterized by the Model

DOI10.1007/978-3-540-69407-6_45MaRDI QIDQ3507457zbMATH OpenOpenAlexFDO

Authors Barnaby Martin

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_45

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)

Recommendations

• On the complexity of the model checking problem
• The complexity of first-order and monadic second-order logic revisited
• Current trends and new perspectives for first-order model checking (invited talk)
• Parameterized complexity of fixed variable logics
• Model-Checking First-Order Logic: Automata and Locality

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Complexity classifications of Boolean constraint satisfaction problems
• Computer Science Logic
• Conjunctive-query containment and constraint satisfaction
• Log Space Recognition and Translation of Parenthesis Languages
• Logical Approaches to Computational Barriers
• On the complexity of H-coloring
• Principles and Practice of Constraint Programming – CP 2004
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(17)

• Complexity parameters for first order classes
• Parameterized complexity of fixed variable logics
• scientific article; zbMATH DE number 1688350 (Why is no real title available?)
• Constraint satisfaction with counting quantifiers
• On the complexity of the model checking problem
• Model-Checking First-Order Logic: Automata and Locality
• The parameterized space complexity of model-checking bounded variable first-order logic
• scientific article; zbMATH DE number 7297863 (Why is no real title available?)
• The tractability frontier of graph-like first-order query sets
• The tractability frontier of graph-like first-order query sets
• A parameterized view on the complexity of dependence logic
• Current trends and new perspectives for first-order model checking (invited talk)
• On the complexity of existential positive queries
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• Parameterized circuit complexity of model-checking on sparse structures
• The model evolution calculus as a first-order DPLL method
• The complexity of first-order and monadic second-order logic revisited

This page was built for publication: First-Order Model Checking Problems Parameterized by the Model

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