Decidability of the Clark's completion semantics for monadic programs and queries

DOI10.1017/S1471068414000660MaRDI QIDQ4592984zbMATH OpenFDO

Authors Levon Haykazyan

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6505

zbMATH Keywords

decidabilityClark's completiongeneral programsmonadic programs

Mathematics Subject Classification ID

Logic programming (68N17) Decidability of theories and sets of sentences (03B25) Semantics in the theory of computing (68Q55)

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. To appear in Theory and Practice of Logic Programming (TPLP)

Recommendations

• Tight, consistent, and computable completions for unrestricted logic programs
• scientific article; zbMATH DE number 4176422
• Complexity and undecidability results for logic programming
• Complete extension of general logic programs
• scientific article; zbMATH DE number 6387492

Cites work

• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 1984523 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Monadic logic programs and functional complexity
• Negation in logic programming
• The accepting power of unary string logic programs
• The decision problem for standard classes

Cited in

(2)

• Decidability of logic program semantics and applications to testing
• scientific article; zbMATH DE number 6387492 (Why is no real title available?)

This page was built for publication: Decidability of the Clark's completion semantics for monadic programs and queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592984)