Translatability and intranslatability results for certain classes of logic programs. Series A: Research report 82

ABSTRACT: In this report, we compare the expressive powers of classes of logic programs that are obtained by constraining the number n of atoms in the bodies of rules. This gives rise to the classes of binary programs (n ≤ 2), unary programs (n ≤ 1) and atomic programs (n = 0). 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 on the classes of logic programs under consideration under the least model semantics. Binary programs are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs. In addition, unary programs are strictly more expressive than atomic programs. This setting remains valid even if we consider normal logic programs, in which negative literals may appear in the bodies of rules, under the stable model semantics. We also take propositional satisfiability into consideration and establish that atomic programs are strictly more expressive than sets of clauses under classical semantics. Finally, we study polynomial, faithful, bu