Decidability of the Clark's completion semantics for monadic programs and queries. Issue 3 (16th December 2014)

• Record Type: Journal Article
• Authors: HAYKAZYAN, LEVON
• Is Part Of: Theory and practice of logic programming. Volume 15:Issue 3(2015)
• Page Start: 402
• Page End: 412
• Publication Date: 2014-12-16
• Subjects: monadic programs, -- general programs, -- Clark's completion, -- decidability; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068414000660
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: There are many different semantics for general logic programs (i.e. programs that use negation in the bodies of clauses). Most of these semantics are Turing complete (in a sense that can be made precise), implying that they are undecidable. To obtain decidability one needs to put additional restrictions on programs and queries. In logic programming it is natural to put restrictions on the underlying first-order language. In this note, we show the decidability of the Clark's completion semantics for monadic general programs and queries.