Complexity of existential positive first-order logic

DOI10.1093/logcom/exr043zbMath1270.03062arXiv1011.4757OpenAlexW2569338977MaRDI QIDQ2843995

Miki Hermann, Florian Richoux, Manuel Bodirsky

Publication date: 27 August 2013

Published in: Journal of Logic and Computation, Mathematical Theory and Computational Practice (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconstraint satisfaction problemsexistential positive first-order logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

On the Complexity of the Model Checking Problem ⋮ Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem

Cites Work

• Unnamed Item
• A comparison of polynomial time reducibilities
• First-Order Model Checking Problems Parameterized by the Model
• Non-dichotomies in Constraint Satisfaction Complexity
• On the Computational Complexity of Monotone Constraint Satisfaction Problems

This page was built for publication: Complexity of existential positive first-order logic