Some (in)translatability results for normal logic programs and propositional theories
Author:
- 1 January 2006
- journal article
- Published by Taylor & Francis in Journal of Applied Non-Classical Logics
- Vol. 16 (1-2)
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 (n) in the bodies of rules. The comparison is based on the existence/nonexistence of polynomial, faithful, and modular (PFM) translation functions between the classes. As a result, we obtain a strict ordering among the classes under consideration. Binary programs (n ⪯ 2) are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs (n ⪯ 1) which, in turn, are strictly more expressive than atomic programs (n = 0). 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 (of the order of ||P|| × log2 |Hb(P)|). Furthermore, we present a p...Keywords
This publication has 40 references indexed in Scilit:
- On the equivalence and range of applicability of graph-based representations of logic programsInformation Processing Letters, 2002
- Representation results for defeasible logicACM Transactions on Computational Logic, 2001
- Characterizations of the disjunctive stable semantics by partial evaluationThe Journal of Logic Programming, 1997
- On the correctness of unfold/fold transformation of normal and extended logic programsThe Journal of Logic Programming, 1995
- Modularity in Logic ProgrammingThe Journal of Logic Programming, 1994
- Propositional semantics for disjunctive logic programsAnnals of Mathematics and Artificial Intelligence, 1994
- Towards a Theory of Declarative Knowledge1988
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- Negation as Failure1978
- The Semantics of Predicate Logic as a Programming LanguageJournal of the ACM, 1976