Complexity of existential positive first-order logic

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

Miki Hermann, Manuel Bodirsky, Florian Richoux

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 complexity; constraint satisfaction problems; existential positive first-order logic

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B10: Classical first-order logic

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)