Some (in)translatability results for normal logic programs and propositional theories

Journal of Applied Non-Classical Logics 16 (1-2):35-86 (2006)
  Copy   BIBTEX

Abstract

In this article, we compare the expressive powers of classes of normal logic programs that are obtained by constraining the number of positive subgoals in the bodies of rules. The comparison is based on the existence/nonexistence of polynomial, faithful, and modular translation functions between the classes. As a result, we obtain a strict ordering among the classes under consideration. Binary programs are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs which, in turn, are strictly more expressive than atomic programs. We also take propositional theories into consideration and prove them to be strictly less expressive than atomic programs. In spite of the gap in expressiveness, we develop a faithful but non-modular translation function from normal programs to propositional theories. We consider this as a breakthrough due to sub-quadratic time complexity |). Furthermore, we present a prototype implementation of the translation function and demonstrate its promising performance with SAT solvers using three benchmark problems.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Formulas in modal logic s4.Katsumi Sasaki - 2010 - Review of Symbolic Logic 3 (4):600-627.
Rules and Arithmetics.Albert Visser - 1999 - Notre Dame Journal of Formal Logic 40 (1):116-140.
The Power of a Propositional Constant.Robert Goldblatt & Tomasz Kowalski - 2012 - Journal of Philosophical Logic (1):1-20.
Propositional quantifiers in modal logic.Kit Fine - 1970 - Theoria 36 (3):336-346.
A survey of propositional realizability logic.Valery Plisko - 2009 - Bulletin of Symbolic Logic 15 (1):1-42.
Interpretations of intuitionist logic in non-normal modal logics.Colin Oakes - 1999 - Journal of Philosophical Logic 28 (1):47-60.
Formal Logic for Informal Logicians.David Sherry - 2006 - Informal Logic 26 (2):199-220.
Normal monomodal logics can simulate all others.Marcus Kracht & Frank Wolter - 1999 - Journal of Symbolic Logic 64 (1):99-138.
Infinitary propositional normal modal logic.Slavian Radev - 1987 - Studia Logica 46 (4):291 - 309.

Analytics

Added to PP
2014-01-21

Downloads
33 (#419,057)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Foundations of Logic Programming.J. W. Lloyd - 1987 - Journal of Symbolic Logic 52 (1):288-289.
The Stable Model Semantics for Logic Programming.Melvin Fitting - 1992 - Journal of Symbolic Logic 57 (1):274-277.

View all 7 references / Add more references