Program maps for characterizing factors of logic programs based on computational behavior

This paper concerns the formalization of our intuition of similar operational behavior of logic programs. We introduce a notion of computational behavior subsumption of logic programs based on a mapping from the symbols of one program to the symbols of another. Greatly improving on previous definitions and results, we present easy to check, syntactic conditions on the mappings (called program maps) which are sufficient to characterize program factors, namely images of a more complicated program under program maps, and whose behavior are reflected in the more complicated program. We show how program maps define an equivalence relation on logic programs based on how programs compute, and determine a partial ordering amongst the classes of programs with equivalent computational behavior. To illustrate the utility of syntactic mappings, we present an operation called composition to merge identical factors manifested in different programs. Program maps are used to characterize 'behavior preserving' operations on logic programs. To show how identifying factors can help elucidate the structure of logic programs, we briefly discuss how the behavior preserving operations, including composition, can form a basis for a method to incrementally construct logic programs from reusable components.