The parameterized space complexity of model-checking bounded variable first-order logic

Yijia Chen, Michael Elberfeld, Moritz Müller

The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational stru…