The complexity of positive first-order logic without equality

DOI10.1145/2071368.2071373MaRDI QIDQ2946653zbMATH OpenOpenAlexWikidataFDO

Authors Florent R. Madelaine, Barnaby Martin

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

Galois connectionquantified constraintsequality-free logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Subsystems of classical logic (including intuitionistic logic) (03B20)

Abstract: We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B. This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(B). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterises definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as B ranges over structures of size at most three. Specifically, each problem is either in Logspace, is NP-complete, is co-NP-complete or is Pspace-complete.

Recommendations

• The complexity of positive first-order logic without equality. II: The four-element case
• The complexity of equivalence, entailment, and minimization in existential positive logic
• On the complexity of the model checking problem

Cited in

(8)

• The lattice and semigroup structure of multipermutations
• Positive Arithmetic Without Exchange Is a Subclassical Logic
• On the complexity of the model checking problem
• The complexity of positive first-order logic without equality. II: The four-element case
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• The complexity of equivalence, entailment, and minimization in existential positive logic
• On the complexity of existential positive queries
• The complexity of quantified constraints using the algebraic formulation

This page was built for publication: The complexity of positive first-order logic without equality

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