{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:54Z","timestamp":1759638594677},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2001,10,22]],"date-time":"2001-10-22T00:00:00Z","timestamp":1003708800000},"content-version":"unspecified","delay-in-days":51,"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":[[2001,9]]},"abstract":"<jats:p>We present a framework for expressing bottom-up algorithms to compute the well-founded \nmodel of non-disjunctive logic programs. Our method is based on the notion of conditional \nfacts and elementary program transformations studied by B<jats:sc>RASS<\/jats:sc> and D<jats:sc>IX<\/jats:sc> (Brass and Dix, \n1994; Brass and Dix, 1999) for disjunctive programs. However, even if we restrict their \nframework to nondisjunctive programs, their \u2018residual program\u2019 can grow to exponential size, \nwhereas for function-free programs our \u2018program remainder\u2019 is always polynomial in the size \nof the extensional database (EDB). We show that particular orderings of our transformations \n(we call them <jats:italic>strategies<\/jats:italic>) correspond to well-known computational methods like the alternating \nfixpoint approach (Van Gelder, 1989; Van Gelder, 1993), the well-founded magic sets method \n(Kemp <jats:italic>et al<\/jats:italic>., 1995) and the magic alternating fixpoint procedure (Morishita, 1996). However, \ndue to the confluence of our calculi (first noted in Brass and Dix, 1998), we come up with \ncomputations of the well-founded model that are provably better than these methods. In contrast \nto other approaches, our transformation method treats magic set transformed programs \ncorrectly, i.e. it always computes a relevant part of the well-founded model of the original \nprogram. These results show that our approach is a valuable tool to analyze, compare, and \noptimize existing evaluation methods or to create new strategies that are automatically proven \nto be correct if they can be described by a sequence of transformations in our framework. We \nhave also developed a prototypical implementation. Experiments illustrate that the theoretical \nresults carry over to the implemented prototype and may be used to optimize real life systems.<\/jats:p>","DOI":"10.1017\/s147106840100103x","type":"journal-article","created":{"date-parts":[[2003,10,16]],"date-time":"2003-10-16T10:51:10Z","timestamp":1066301470000},"page":"497-538","source":"Crossref","is-referenced-by-count":22,"title":["Transformation-based bottom-up computation of the well-founded model"],"prefix":"10.1017","volume":"1","author":[{"given":"STEFAN","family":"BRASS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00dcRGEN","family":"DIX","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BURKHARD","family":"FREITAG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ULRICH","family":"ZUKOWSKI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2001,10,22]]},"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\/S147106840100103X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T18:50:24Z","timestamp":1554144624000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106840100103X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,9]]},"references-count":0,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2001,9]]}},"alternative-id":["S147106840100103X"],"URL":"https:\/\/doi.org\/10.1017\/s147106840100103x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,9]]}}}