The Unexpected side of Logic Programming
Lucrezia Maddalena Mosconi

Abstract:
Through this thesis, we investigate computational approaches to surprise. We define a novel computational framework, CompLogDL, building on an existing blueprint by Sileno et al.: both rest on the Simplicity Theoretic definition of surprise, according to which an event is unexpected if it is more complex to generate than it is to describe. Our contribution through this thesis is two-fold.
At a conceptual level, we provide a formal argument against the received view of surprise, arguing that surprise ought not to be defined in terms of low probabilities. We first show that such a definition is neither necessary nor sufficient, and then that probabilistic interpretations encounter severe difficulties when predicting surprise. We then observe that this difficulties can easily overcome by a Simplicity-based definition of surprise, according to which an event is unexpected if it is more complex to generate than it is to describe. On this basis, we define a novel computational framework, CompLogDL, informed by a previous proposal by Sileno et al.. At a formal level, we introduce the syntax and semantics of CompLogDL: its inference mechanism is made of two separate components, one computing the description complexity of an instance and the other computing its generation complexity. We specify each inference task and analyze their complexity in detail.