15(3)4

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

Levon Haykazyan
Mathematical Institute, University of Oxford,

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.

PDF Version

 

Bibtex (Use it for references)

@article{KEYWORD,
journal = {Theory and Practice of Logic Programming},
publisher = {Cambridge University Press},
author = {Levon Haykazyan},
title = {Decidability of the Clark’s completion semantics for monadic programs and queries },
volume = {15},
number = {3},
year = {2015},
pages = {402 – 412}
}