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

Barnaby Martin

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 sati…