# Back And Forth Between Rules And Se-Models (Extended Version)⋆

Martin Slota and Jo˜ao Leite CENTRIA & Departamento de Inform´atica Universidade Nova de Lisboa Quinta da Torre 2829-516 Caparica, Portugal Abstract. Rules in logic programming encode information about mutual interdependencies between literals that is not captured by any of the commonly used semantics. This information becomes essential as soon as a program needs to be modified or further manipulated.

We argue that, in these cases, a program should not be viewed solely as the set of its models. Instead, it should be viewed and manipulated as the *set of sets* of models of each rule inside it. With this in mind, we investigate and highlight relations between the SE-model semantics and individual rules. We identify a set of representatives of rule equivalence classes induced by SE-models, and so pinpoint the exact expressivity of this semantics with respect to a single rule. We also characterise the class of sets of SE-interpretations representable by a single rule. Finally, we discuss the introduction of two notions of equivalence, both stronger than *strong equivalence* [1] and weaker than *strong update equivalence* [2], which seem more suitable whenever the dependency information found in rules is of interest.

## 1 Motivation

In this paper we take a closer look at the relationship between the SE-model semantics and individual rules of a logic program. We identify a set of representatives of rule equivalence classes, which we dub *canonical rules*, characterise the class of sets of SE-interpretations that are representable by a single rule, and show how the corresponding canonical rules can be reconstructed from them. We believe that these results pave the way to view and manipulate a logic program as the set of sets of SE*-models* of each rule inside it. This is important in situations when the set of SE-models of the whole program fails to capture essential information encoded in individual rules inside it, such as when the program needs to be modified or further manipulated. With this in mind, we briefly discuss two new notions of equivalence, stronger than *strong* equivalence [1] and weaker than *strong update equivalence* [2].

In many extensions of Answer-Set Programming, individual rules of a program are treated as first-class citizens - apart from their prime role of encoding the answer sets
⋆ This is an extended version of the paper accepted for publication at LPNMR 2011.

Changes on March 1, 2011: minor substitutions to be in line with the LPNMR version.