ECAI 2004 Conference Paper

Synonymous Theories in Answer Set Programming and Equilibrium Logic

David Pearce, Agustín Valverde

The study of strong equivalence between logic programs or nonmonotonic theories under answer set semantics is extended to the case where the programs or theories concerned are formulated in different languages. We suggest that theories in different languages be considered equivalent in the strong sense or synonymous if and only if each is bijectively interpretable (hence translatable) into the other. Since the logic of here-and-there, which provides a suitable foundation for answer set programming, has the Beth property, we can easily give model-theoretic conditions that are equivalent to bijective interpretability. These conditions involve mappings between the models of the two theories that, in particular, preserve the property of being an answer set or equilibrium model.

Keywords: Synonymous theories, Equilibrium logic, Answer set programming

Citation: David Pearce, Agustín Valverde: Synonymous Theories in Answer Set Programming and Equilibrium Logic. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.388-392.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).