Conflict, Consistency and Truth-Dependencies in Graph Representations of Answer Set Logic Programs

In this paper we propose a formalization of the features that a graph representation of logic programs under the answers set semantics should in our opinion exhibit in order to be a satisfactory and useful representation formalism. We introduce a concept of isomorphism between a program and the corresponding graph. Isomorphic graph representations guarantee that the graph corresponding to a program is unique, and that the original program can be reconstructed from the graph. We prove that the isomorphism is possible only if a graph representation formalism is able to distinguish the cycles occurring in the program, and the different connections among them. We consider and discuss some of the existing graph representations. We argue that understanding cycles and their connections is a key point for understanding program behavior and for checking consistency, for being then able to create, debug and combine good programs, and for developing program analysis techniques.