Hostname: page-component-6898cfcb55-cbk24 Total loading time: 0 Render date: 2026-11-12T00:02:42.918Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  16 December 2014

LEVON HAYKAZYAN
LEVON HAYKAZYAN*
Affiliation:
Mathematical Institute, University of Oxford, Woodstock Road, Oxford, OX2 6GG, UK (email: haykazyanl@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

monadic programsgeneral programsClark's completiondecidability

Information

Type
Technical Note
Information
Theory and Practice of Logic Programming , Volume 15 , Issue 3 , May 2015, pp. 402 - 412
Copyright
Copyright © Cambridge University Press 2014 

References

Börger, E., Grädel, E. and Gurevich, Y. 1997. The Classical Decision Problem. Springer Verlag, Berlin.Google Scholar
Clark, K. L. 1978. Negation as failure. In Logic and Databases, Gallaire, H. and Minker, J., Eds. Plenum, New York, 293–322.Google Scholar
Gurevich, Y. 1966. On the effective recognizing of satisfiability of predicate formulas. Algebra and Logic 5, 25–55.Google Scholar
Gurevich, Y. 1976. The decision problem for standard classes. Journal of Symbolic Logic 21, 2, 460–464.CrossRefGoogle Scholar
Kunen, K. 1987. Negation in logic programming. Journal of Logic Programming 4, 289–308.CrossRefGoogle Scholar
Lloyd, J. W. 1984. Foundations of Logic Programming. Springer-Verlag, Berlin.Google Scholar
Matos, A. B. 1997. Monadic logic programs and functional complexity. Theoretical Computer Science 176, 175–204.Google Scholar
Matsushita, T. and Runciman, C. 2001. The accepting power of unary string logic programs. Theoretical Computer Science 266, 59–79.CrossRefGoogle Scholar
Meyer, A. R. 1975. Weak monadic second order theory of successor is not elementary-recursive. In Logic Colloquium, Parikh, R., Ed. Springer, Berlin Heidelberg, 132–154.Google Scholar
Rabin, M. O. 1969. Decidability of second order theories and automata on infinite trees. Transactions of The American Mathematical Society 141, 1–35.Google Scholar
Shepherdson, J. C. 2002. Language and equality theory in logic programming. In Logic, Meaning and Computation, Hendricks, V. F., Symons, J., Dalen, D., Kuipers, T. A., Seidenfeld, T., Suppes, P., Woleski, J., Anderson, C. A., and Zelny, M., Eds. Springer, Netherlands, 365–392.Google Scholar