An Extension of Van Gelder's Alternating Fixpoint to Magic Programs

✍ Scribed by Shinichi Morishita

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 633 KB
• Volume: 52
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0038

✦ Synopsis

We study the application of the magic-sets transformation technique to Datalog c (function-free programs with negation) that may not have two-valued well-founded models. In this general setting, the wellfounded model of the original program does not always agree with the well-founded model of the magic program derived by commonly used left-to-right sideways information-passing strategies on the query. In order to correct this disagreement we present a novel method that is obtained by slightly and naturally tailoring Van Gelder's alternating fixpoint technique to any magic program.