Tractable Combinations of Theories via Sampling
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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.
Details
Original language | English |
---|---|
Title of host publication | Logics in Artificial Intelligence - 17th European Conference, JELIA 2021, Proceedings |
Editors | Wolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak |
Publisher | Springer, Berlin [u. a.] |
Pages | 133-146 |
Number of pages | 14 |
ISBN (print) | 9783030757748 |
Publication status | Published - 2021 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science, Volume 12678 |
---|---|
ISSN | 0302-9743 |
Conference
Title | 17th European Conference on Logics in Artificial Intelligence |
---|---|
Abbreviated title | JELIA 2021 |
Conference number | 17 |
Duration | 17 - 20 May 2021 |
Location | online |
City | Klagenfurt |
Country | Austria |
External IDs
ORCID | /0000-0001-8228-3611/work/142241056 |
---|