The complexity of equivalence, entailment, and minimization in existential positive logic

DOI10.1016/J.JCSS.2014.10.002zbMath1401.03030OpenAlexW2022388196MaRDI QIDQ473196

Hubie Chen, Simone Bova

Publication date: 24 November 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.10.002

zbMATH Keywords

equivalencecomputational complexityentailmentexistential positive logicfinite-variable logics

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Cites Work

• Unnamed Item
• The core of a graph
• The complexity of constraint satisfaction games and QCSP
• Equivalences Among Relational Expressions with the Union and Difference Operators
• On the complexity of existential positive queries

This page was built for publication: The complexity of equivalence, entailment, and minimization in existential positive logic