{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:55:44Z","timestamp":1747810544726},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T00:00:00Z","timestamp":1252886400000},"content-version":"unspecified","delay-in-days":0,"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":[[2009,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A recent framework of relativized hyperequivalence of programs offers a unifying generalization of strong and uniform equivalence. It seems to be especially well suited for applications in program optimization and modular programming due to its flexibility that allows us to restrict, independently of each other, the head and body alphabets in context programs. We study relativized hyperequivalence for the three semantics of logic programs given by stable, supported, and supported minimal models. For each semantics, we identify four types of contexts, depending on whether the head and body alphabets are given directly or as the<jats:italic>complement<\/jats:italic>of a given set. Hyperequivalence relative to contexts where the head and body alphabets are specified directly has been studied before. In this paper, we establish the complexity of deciding relativized hyperequivalence with respect to the three other types of context programs.<\/jats:p>","DOI":"10.1017\/s1471068409990159","type":"journal-article","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T08:21:20Z","timestamp":1252916480000},"page":"781-819","source":"Crossref","is-referenced-by-count":5,"title":["Relativized hyperequivalence of logic programs for modular programming"],"prefix":"10.1017","volume":"9","author":[{"given":"MIROS\u0141AW","family":"TRUSZCZY\u0143SKI","sequence":"first","affiliation":[]},{"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,9,14]]},"reference":[{"key":"S1471068409990159_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001819"},{"key":"S1471068409990159_ref26","first-page":"412","volume-title":"Proc. of the 17th European Conference on Artificial Intelligence (ECAI 2006)","author":"Oikarinen","year":"2006"},{"key":"S1471068409990159_ref25","first-page":"458","volume-title":"Proc. of the 22nd National Conference on Artificial Intelligence (AAAI 2007)","author":"Oetsch","year":"2007"},{"key":"S1471068409990159_ref22","first-page":"170","volume-title":"Proc. of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR 2002)","author":"Lin","year":"2002"},{"key":"S1471068409990159_ref21","first-page":"23","volume-title":"Proc. of the 11th International Conference on Logic Programming (ICLP 1994)","author":"Lifschitz","year":"1994"},{"key":"S1471068409990159_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068409990159_ref18","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068409990159_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45632-5_16"},{"key":"S1471068409990159_ref17","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-540-30227-8_17","volume-title":"Proc. of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004)","author":"Inoue","year":"2004"},{"key":"S1471068409990159_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_3"},{"key":"S1471068409990159_ref12","first-page":"134","volume-title":"Proc. of the 16th Annual ACM Symposium on Principles of Programming Languages (POPL 1989)","author":"Gaifman","year":"1989"},{"key":"S1471068409990159_ref10","first-page":"97","volume-title":"Proc. of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)","author":"Eiter","year":"2005"},{"key":"S1471068409990159_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068409990159_ref7","first-page":"224","volume-title":"Proc. of the 19th International Conference on Logic Programming (ICLP 2003)","author":"Eiter","year":"2003"},{"key":"S1471068409990159_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840200159X"},{"key":"S1471068409990159_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1244000"},{"key":"S1471068409990159_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"S1471068409990159_ref4","first-page":"346","volume-title":"Proc. of the 22nd International Conference (ICLP 2006)","author":"Cabalar","year":"2006"},{"key":"S1471068409990159_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S1471068409990159_ref11","first-page":"483","volume-title":"Proc. of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2004)","author":"Erdogan","year":"2004"},{"key":"S1471068409990159_ref1","first-page":"493","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics","author":"Apt","year":"1990"},{"key":"S1471068409990159_ref30","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-540-30227-8_16","volume-title":"Proc. of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004)","author":"Woltran","year":"2004"},{"key":"S1471068409990159_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50021-X"},{"key":"S1471068409990159_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(96)00115-X"},{"key":"S1471068409990159_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)10001-2"},{"key":"S1471068409990159_ref24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068409990159_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00207-2"},{"key":"S1471068409990159_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068409990159_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72200-7_16"},{"key":"S1471068409990159_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9119-8"},{"key":"S1471068409990159_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068407003250"}],"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\/S1471068409990159","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T18:54:47Z","timestamp":1685127287000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068409990159\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,14]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["S1471068409990159"],"URL":"https:\/\/doi.org\/10.1017\/s1471068409990159","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,14]]}}}