The semantics of Gringo and infinitary propositional formulas
Amelia Harrison, Vladimir Lifschitz, Fangkai Yang · 2014
Input languages of answer set solvers are based on the mathe-matically simple concept of a stable model. But many useful constructs available in these languages, including local vari-ables, conditional literals, and aggregates, cannot be easily explained in terms of stable models in the sense of the origi-nal definition of this concept and its straightforward general-izations. Manuals written by designers of answer set solvers usually explain such constructs using examples and informal comments that appeal to the user’s intuition, without refer-ences to any precise semantics. We propose to approach the problem of defining the semantics of GRINGO programs by translating them into the language of infinitary propositional formulas. This semantics allows us to study equivalent trans-formations of GRINGO programs using natural deduction in infinitary propositional logic, so that the properties of these programs can be more precisely characterized. In this way, we aim to create a foundation on which important issues such as the correctness of GRINGO programs and optimiza-tion methods may be more formally studied. 1