'Logic programming and aggregates: Analyzing Semantics Using Approximation Fixpoint Theory'

Dates: 
Friday, June 4, 2021 - 1:05pm
Location: 
Zoom - contact events@cs.stonybrook.edu for Zoom info.
Event Description: 

Guest speakers Marc Denecker and Linde Vanbesien, KU Leuven

Abstract:
Aggregates such as cardinality, sum, min, max  are expressive higher

order language constructs. While they are easily understood by humans

and have many useful applications, adding aggregates to logic

programming and extensions such as datalog and answer set programming

(ASP) has proven to be challenging. The literature offers many

approaches that are not always compatible.  In this seminar we revisit

one of these approaches, the one based on Approximation Fixpoint

Theory (AFT).



We begin with a technical contribution, showing how any 3-valued truth

assignment for rule bodies with aggregates induces well-founded,

stable and Kripke Kleene semantics. We then look at how to plug in

aggregate constructs in the informal semantics of logic programs as

inductive definitions, and argue that the well-founded semantics of

aggregate logic programs formalizes this definitional view. We also

briefly point at some unbearable weaknesses of the aggregate logic

programming formalism from a KR point of view, and show the easy way

to eliminate them. This results in expressive and natural language

constructs that can be integrated in classical logics.



The last part of the seminar is technical again and focuses on  the

aggregate answer set programming. We introduce the abstract notion of

a ternary satisfaction relation and define stable semantics in terms

of it. We show that ternary satisfaction relations  bridge the gap

between the standard Gelfond-Lifschitz reduct, and stable semantics as

defined in the framework of AFT. We analyse the properties of ternary

satisfaction relations for handling aggregates in ASP programs.

Finally, we show how different methods for handling aggregates taken

from the literature can be described in the framework and we study the

corresponding ternary satisfaction relations.

Hosted By: 
Annie Liu
Computed Event Type: 
Mis