On the Complexity of the Model Checking Problem

DOI10.1137/140965715zbMath1393.68078arXiv1210.6893OpenAlexW2963983432MaRDI QIDQ3176188

Florent R. Madelaine, Barnaby Martin

Publication date: 19 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.6893

zbMATH Keywords

computational complexityGalois connectionuniversal algebralogic in computer sciencequantified constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Specification and verification (program logics, model checking, etc.) (68Q60) Galois correspondences, closure operators (in relation to ordered sets) (06A15)

Related Items

The lattice and semigroup structure of multipermutations

Cites Work

• Unnamed Item
• Finite model theory and its applications.
• The complexity of constraint satisfaction games and QCSP
• On the complexity of H-coloring
• Conjunctive-query containment and constraint satisfaction
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Complexity of existential positive first-order logic
• Meditations on Quantified Constraint Satisfaction
• The Complexity of Positive First-Order Logic without Equality
• QCSP on Partially Reflexive Forests
• First-Order Model Checking Problems Parameterized by the Model
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Log Space Recognition and Translation of Parenthesis Languages
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Logical Approaches to Computational Barriers
• Principles and Practice of Constraint Programming – CP 2004