Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three

Details Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three

2008-08-05

arxiv.org/abs/0808.0647v1

Computer Science

Computational Complexity

Scientific paper

We study the model checking problem, for fixed structures A, over positive equality-free first-order logic -- a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(A). We prove a complete complexity classification for this problem when A ranges over 1.) boolean structures and 2.) digraphs of size (less than or equal to) three. The former class displays dichotomy between Logspace and Pspace-complete, while the latter class displays tetrachotomy between Logspace, NP-complete, co-NP-complete and Pspace-complete.

Affiliated with

Also associated with

No associations

Rating

Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-550292