{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T23:26:50Z","timestamp":1656372410957},"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":"The well-founded semantics is one of the most widely studied and used semantics of logic \nprograms with negation. In the case of finite propositional programs, it can be computed \nin polynomial time, more specifically, in O<\/jats:italic>([mid ]At<\/jats:italic>(P<\/jats:italic>)[mid ] \u00d7 size<\/jats:italic>(P<\/jats:italic>)) \nsteps, where size<\/jats:italic>(P<\/jats:italic>) denotes \nthe total number of occurrences of atoms in a logic program P<\/jats:italic>. This bound is achieved by \nan algorithm introduced by Van Gelder and known as the alternating-fixpoint algorithm. \nImproving on the alternating-fixpoint algorithm turned out to be difficult. In this paper we \nstudy extensions and modifications of the alternating-fixpoint approach. We then restrict our \nattention to the class of programs whose rules have no more than one positive occurrence of \nan atom in their bodies. For programs in that class we propose a new implementation of the \nalternating-fixpoint method in which false atoms are computed in a top-down fashion. We \nshow that our algorithm is faster than other known algorithms and that for a wide class of \nprograms it is linear and so, asymptotically optimal.<\/jats:p>","DOI":"10.1017\/s1471068401001053","type":"journal-article","created":{"date-parts":[[2008,8,14]],"date-time":"2008-08-14T06:46:23Z","timestamp":1218696383000},"page":"591-609","source":"Crossref","is-referenced-by-count":3,"title":["On the problem of computing the well-founded semantics"],"prefix":"10.1017","volume":"1","author":[{"given":"ZBIGNIEW","family":"LONC","sequence":"first","affiliation":[]},{"given":"MIROS\u0141AW","family":"TRUSZCZY\u0143SKI","sequence":"additional","affiliation":[]}],"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\/S1471068401001053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T14:50:25Z","timestamp":1554130225000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068401001053\/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":["S1471068401001053"],"URL":"https:\/\/doi.org\/10.1017\/s1471068401001053","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,9]]}}}