{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T15:13:28Z","timestamp":1696086808792},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643684369","type":"print"},{"value":"9781643684376","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>This paper is concerned with a refutation system (proof system) for a class of linear constraint systems called difference constraint systems (DCS). In particular, we study the refutability of DCSs in the unit refutation (UR) system. Recall that a difference constraint is a linear relationship of the form: xi-xj \u2264 bij and a DCS is a conjunction of such constraints. Associated with a refutation system are three important features, viz., (a) Soundness, (b) Completeness, and (c) Efficiency. The UR system is sound and efficient; however, it is incomplete, in that unsatisfiable DCSs may not have unit refutations. We establish that this refutation system is efficient in that there exists a tractable algorithm for determining if a DCS has a UR. Investigating weak (incomplete) refutation systems leads to a better understanding of the inference rules required for establishing contradictions in the given constraint system. Thus, this study is well-motivated. Despite the fact that unit refutations can be exponentially long in terms of the input system size, we provide a compact representation of these refutations. This compact representation is an important contribution of this paper.<\/jats:p>","DOI":"10.3233\/faia230520","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:19:12Z","timestamp":1695979152000},"source":"Crossref","is-referenced-by-count":0,"title":["Unit Refutations of Difference Constraint Systems"],"prefix":"10.3233","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[{"name":"LDCSEE, West Virginia University, Morgantown, West Virginia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Wojciechowski","sequence":"additional","affiliation":[{"name":"LDCSEE, West Virginia University, Morgantown, West Virginia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:19:15Z","timestamp":1695979155000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230520","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}