Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
<|reference_start|>Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation): 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 computational complexity separation but also confirm the algebraic tractability conjecture stating that tractability origins from a certain system of operations preserving B. The establishment of the dichotomy was in fact preceded by a number of similar results for stronger conditions of this type, i.e. for system of operations covering not necessarily all tractable finite-domain CSPs.   A similar, infinite-domain algebraic tractability conjecture is known for first-order reducts of countably infinite finitely bounded homogeneous structures and is currently wide open. In particular, with an exception of a quasi near-unanimity operation there are no known systems of operations implying tractability in this regime. This paper changes the state-of-the-art and provides a proof that a chain of quasi directed Jonsson operations imply tractability and bounded width for a large and natural class of infinite structures.<|reference_end|>
@article{wrona2024quasi,
    title={Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions
  of symmetric binary cores with free amalgamation)},
    author={Michal Wrona},
    journal={arXiv preprint arXiv:2402.16540},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16540},
    primaryClass={cs.LO}
}