Aggregate semantics for propositional answer set programs

M Alviano, W Faber, M Gebser - Theory and Practice of Logic …, 2023 - cambridge.org
Theory and Practice of Logic Programming, 2023cambridge.org
Answer set programming (ASP) emerged in the late 1990s as a paradigm for knowledge
representation and reasoning. The attractiveness of ASP builds on an expressive high-level
modeling language along with the availability of powerful off-the-shelf solving systems.
While the utility of incorporating aggregate expressions in the modeling language has been
realized almost simultaneously with the inception of the first ASP solving systems, a general
semantics of aggregates and its efficient implementation have been long-standing …
Answer set programming (ASP) emerged in the late 1990s as a paradigm for knowledge representation and reasoning. The attractiveness of ASP builds on an expressive high-level modeling language along with the availability of powerful off-the-shelf solving systems. While the utility of incorporating aggregate expressions in the modeling language has been realized almost simultaneously with the inception of the first ASP solving systems, a general semantics of aggregates and its efficient implementation have been long-standing challenges. Aggregates have been proposed and widely used in database systems, and also in the deductive database language Datalog, which is one of the main precursors of ASP. The use of aggregates was, however, still restricted in Datalog (by either disallowing recursion or only allowing monotone aggregates), while several ways to integrate unrestricted aggregates evolved in the context of ASP. In this survey, we pick up at this point of development by presenting and comparing the main aggregate semantics that have been proposed for propositional ASP programs. We highlight crucial properties such as computational complexity and expressive power, and outline the capabilities and limitations of different approaches by illustrative examples.
Cambridge University Press
顯示最佳搜尋結果。 查看所有結果