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

DOI10.1017/S1471068414000660zbMATH Open1379.68071arXiv1410.6505MaRDI QIDQ4592984FDOQ4592984

Authors: Levon Haykazyan 

Publication date: 9 November 2017

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

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)

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

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

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)

Cites Work

• Decidability of Second-Order Theories and Automata on Infinite Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Negation in logic programming
• Title not available (Why is that?)
• Monadic logic programs and functional complexity
• The decision problem for standard classes
• Title not available (Why is that?)
• The accepting power of unary string logic programs

Cited In (2)

• Decidability of logic program semantics and applications to testing
• Title not available (Why is that?)

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)