Model-checking positive equality free logic on a fixed structure
(direttissima)
Model-checking positive equality free logic on a fixed structure
(direttissima)
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classes are Logspace, NP-complete, co-NP-complete and Pspace-complete. The previous proof of this result relied on notions from universal algebra and core-like structures called U-X-cores. This …