Binary logic programs can be obtained from ordinary logic programs by a binarizing transformation. In most cases, binary programs
obtained by this way are less efficient than the original programs. Demoen [
2] showed an interesting example of a logic program whose computational behavior was improved if it was transformed to a binary
program and then specialized by partial deduction.
The class of so called B-stratifiable logic programs is defined. It is shown that for every B-stratifiable logic program,
binarization and subsequent partial deduction produce a binary program which usually has a better computational behavior than
the original one. Both binarization and partial deduction can be automated.