2000/11/08 by Stefan Brass, Juergen Dix, Brass, Stefan +5
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #I.2.3 #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.LO
paper · pdf · doi:10.48550/arxiv.cs/0011013
43 pages, 3 figures
arxiv created 2000/11/08 · openalex publication_date 2000/11/08 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a framework for expressing bottom-up algorithms to compute the well-founded model of non-disjunctive logic programs. Our method is based on the notion of conditional facts and elementary program transformations studied by Brass and Dix for disjunctive programs. However, even if we restrict their framework to nondisjunctive programs, their residual program can grow to exponential size, whereas for function-free programs our program remainder is always polynomial in the size of the extensional database (EDB). We show that particular orderings of our transformations (we call them strategies) correspond to well-known computational methods like the alternating fixpoint approach, the well-founded magic sets method and the magic alternating fixpoint procedure. However, due to the confluence of our calculi, we come up with computations of the well-founded model that are provably better than these methods. In contrast to other approaches, our transformation method treats magic set transformed programs correctly, i.e. it always computes a relevant part of the well-founded model of the original program.