Logic Programming as Hypergraph Rewriting

Logic Programming and (Hyper-)Graph Rewriting are two well known fields of Computer Science. In this paper we show how to model logic program computations through algebraic techniques familiar to the graph rewriting community. Clauses of a logic program are represented by graph productions, goals by suitable hypergraphs (called jungles), and resolution steps by an algebraic construction involving three pushouts. The correspondence between the two formalisms is further analyzed by providing a precise algebraic characterization of specialization and unfolding of clauses.