Showing cs.LOShow all
2 papers · 1 filter
cs.LO2024
Model-checking positive equality free logic on a fixed structure (direttissima)
Manuel Bodirsky, Marcin Kozik, Florent Madelaine +2
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 classe…
cs.LO2024
Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
Michal Wrona
Every CSP(B) for a finite structure B is either in P or it is NP-complete but the proofs of the finite-domain CSP dichotomy by Andrei Bulatov and Dimitryi Zhuk not only show the co…