Characterising Relativised Strong Equivalence with Projection for Non-ground Answer-Set Programs

Abstract

Starting with the seminal work on strong equivalence by Lifschitz, Pearce, and Valverde, many different advanced notions of program equivalence have been studied in the area of answer-set programming (ASP). In particular, relativised strong equivalence with projection has been introduced as a generalisation of strong equivalence by parameterising,on the one hand, the alphabet of the context programs used for checking program equivalence as well as, on the other hand, allowing the filtering of auxiliary atoms. Like many other advanced equivalence notions, it was introduced originally for propositional programs, along with model-theoretic concepts providing characterisations when equivalence between two programs hold. In this paper, we extend these concepts and characterisations to the general case of non-ground programs.