Tractable Combinations of Theories via Sampling

DOI10.1007/978-3-030-75775-5_10MaRDI QIDQ6355132arXivFDO

Authors Manuel Bodirsky, Johannes Greiner

Publication date 2 December 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-75775-5_10

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

arXiv classification

cs.CCmath.LO

Abstract: For a first-order theory $T$, the Constraint Satisfaction Problem of $T$ is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of $T$. In this article we develop sufficient conditions for polynomial-time tractability of the constraint satisfaction problem for the union of two theories with disjoint relational signatures. To this end, we introduce the concept of sampling for theories and show that samplings can be applied to examples which are not covered by the seminal result of Nelson and Oppen.

This page was built for publication: Tractable Combinations of Theories via Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355132)