{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T02:18:54Z","timestamp":1648606734154},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2002,3,25]],"date-time":"2002-03-25T00:00:00Z","timestamp":1017014400000},"content-version":"unspecified","delay-in-days":24,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2002,3]]},"abstract":"<jats:p>Complementation, the inverse of the reduced product operation, is a technique for systematically \nfinding minimal decompositions of abstract domains. Fil\u00e9 and Ranzato advanced \nthe state of the art by introducing a simple method for computing a complement. As an \napplication, they considered the extraction by complementation of the pair-sharing domain \n<jats:italic>PS<\/jats:italic> from the Jacobs and Langen's set-sharing domain <jats:italic>SH<\/jats:italic>. However, since the result of this \noperation was still <jats:italic>SH<\/jats:italic>, they concluded that <jats:italic>PS<\/jats:italic> was too abstract for this. Here, we show that \nthe source of this result lies not with <jats:italic>PS<\/jats:italic> but with <jats:italic>SH<\/jats:italic> and, more precisely, with the redundant \ninformation contained in <jats:italic>SH<\/jats:italic> with respect to ground-dependencies and pair-sharing. In fact, \na proper decomposition is obtained if the non-redundant version of <jats:italic>SH<\/jats:italic>, <jats:italic>PSD<\/jats:italic>, is substituted \nfor <jats:italic>SH<\/jats:italic>. To establish the results for <jats:italic>PSD<\/jats:italic>, we define a general schema for subdomains of <jats:italic>SH<\/jats:italic> \nthat includes <jats:italic>PSD<\/jats:italic> and <jats:italic>Def<\/jats:italic> as special cases. This sheds new light on the structure of <jats:italic>PSD<\/jats:italic> \nand exposes a natural though unexpected connection between <jats:italic>Def<\/jats:italic> and <jats:italic>PSD<\/jats:italic>. Moreover, we \nsubstantiate the claim that complementation <jats:italic>alone<\/jats:italic> is not sufficient to obtain <jats:italic>truly minimal<\/jats:italic> \ndecompositions of domains. The right solution to this problem is to <jats:italic>first<\/jats:italic> remove redundancies \nby computing the quotient of the domain with respect to the observable behavior, and only \n<jats:italic>then<\/jats:italic> decompose it by complementation.<\/jats:p>","DOI":"10.1017\/s1471068401001351","type":"journal-article","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T05:36:33Z","timestamp":1149226593000},"page":"233-261","source":"Crossref","is-referenced-by-count":1,"title":["Decomposing non-redundant sharing by complementation"],"prefix":"10.1017","volume":"2","author":[{"given":"ENEA","family":"ZAFFANELLA","sequence":"first","affiliation":[]},{"given":"PATRICIA M.","family":"HILL","sequence":"additional","affiliation":[]},{"given":"ROBERTO","family":"BAGNARA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2002,3,25]]},"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068401001351","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T15:43:44Z","timestamp":1554047024000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068401001351\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,3]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,3]]}},"alternative-id":["S1471068401001351"],"URL":"https:\/\/doi.org\/10.1017\/s1471068401001351","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,3]]}}}