Tractable Combinations of Theories via Sampling

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

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

OriginalspracheEnglisch
TitelLogics in Artificial Intelligence - 17th European Conference, JELIA 2021, Proceedings
Redakteure/-innenWolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak
Herausgeber (Verlag)Springer, Berlin [u. a.]
Seiten133-146
Seitenumfang14
ISBN (Print)9783030757748
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 12678
ISSN0302-9743

Konferenz

Titel17th European Conference on Logics in Artificial Intelligence
KurztitelJELIA 2021
Veranstaltungsnummer17
Dauer17 - 20 Mai 2021
Ortonline
StadtKlagenfurt
LandÖsterreich

Externe IDs

ORCID /0000-0001-8228-3611/work/142241056

Schlagworte