TCS / Research / Publications / Translatability and Intranslatability Results for Certain Classes of Logic Programs
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Translatability and Intranslatability Results for Certain Classes of Logic Programs

Reference:

Tomi Janhunen. Translatability and intranslatability results for certain classes of logic programs. Research Report A82, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, November 2003.

Abstract:

In this report, we compare the expressive powers of classes of logic programs that are obtained by constraining the number of atoms in the bodies of rules. This gives rise to the classes of binary programs (at most two atoms), unary programs (at most one atom) and atomic programs (no atoms). 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, but non-modular alternatives to PFM translation functions that do not exist. We obtain a breakthrough in this respect by showing that an arbitrary normal logic program can be reduced to set of clauses using a faithful translation function in time proportional to the length of the program times the logarithm of the number of atoms appearing in the program. As an implication of this result, the classes of logic programs under consideration become equally expressive if measured in terms of polynomial and faithful translation functions.

Keywords:

modularity, translation function, expressive power

Suggested BibTeX entry:

@techreport{HUT-TCS-A82,
    address = {Espoo, Finland},
    author = {Tomi Janhunen},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {November},
    number = {A82},
    pages = {88},
    title = {Translatability and Intranslatability Results for Certain Classes of Logic Programs},
    type = {Research Report},
    year = {2003},
}

PostScript (1 MB)
GZipped PostScript (445 kB)
PDF (674 kB)

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.