Dichotomies and Duality in First-order Model Checking Problems
<|reference_start|>Dichotomies and Duality in First-order Model Checking Problems: We study the complexity of the model checking problem, for fixed model A, over certain fragments L of first-order logic. These are sometimes known as the expression complexities of L. We obtain various complexity classification theorems for these logics L as each ranges over models A, in the spirit of the dichotomy conjecture for the Constraint Satisfaction Problem -- which itself may be seen as the model checking problem for existential conjunctive positive first-order logic.<|reference_end|>
@article{martin2006dichotomies,
    title={Dichotomies and Duality in First-order Model Checking Problems},
    author={Barnaby Martin},
    journal={arXiv preprint arXiv:cs/0609022},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609022},
    primaryClass={cs.LO cs.CC}
}