Can I read The Complexity of Positive First-order Logic Without Equality on EtoBox?

The Complexity of Positive First-order Logic Without Equality by Madelaine, Florent; Martin, Barnaby is a scholarly article available to read on EtoBox.

What is The Complexity of Positive First-order Logic Without Equality about?

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.

Author

Madelaine, Florent; Martin, Barnaby

Published

2010

Language

EN