Convegno Italiano di Logica Computazionale

cilc'16, 20-22 giugno 2016


Elena Bellodi
Integration of Logic and Probability in Inductive and Terminological Reasoning:

Abstract: In Inductive and Terminological Reasoning representing uncertain information is crucial for modeling real world domains. This has been fully recognized both in the field of Logic Programming and of Description Logics (DLs), with the introduction of probabilistic logic languages (PLL) in logic and with various probabilistic extensions of DLs respectively. In this work, we consider the distribution semantics and face the problem of learning PLLs and expressing and reasoning with probabilistic DLs. For PLLs, we present a parameter learning algorithm (EMBLEM) and two structure learning algorithms (SLIPCASE, SLIPCOVER): EMBLEM is based on the Expectation Maximization method and efficiently computes the expectations directly on the Binary Decision Diagram built for inference. It is embedded in both SLIPCASE and SLIPCOVER. The algorithms were tested on real world relational datasets and showed superior performance in almost all cases with respect to the state of the art. We then transposed both the distribution semantics and the inference techniques based on BDDs to DLs, developing a probabilistic semantics (DISPONTE) and an algorithm (BUNDLE) that computes the probability of queries over DISPONTE DLs by encoding their explanations in BDDs. We show that BUNDLE is competitive with the probabilistic reasoner PRONTO on a real probabilistic ontology.

Eugenio Omodeo and Alberto Policriti
Martin Davis on Computability, Computational Logic, and Mathematical Foundations

Abstract: Davis’s multi-faceted scientific activity lies at the barycentre of computability, theoretical computer science, foundations of mathematics, philosophy,and draws its unitary vision from his deep involvement in Logic. He has been a trailblazer of the field today known as ‘automated reasoning’: already in the 1950s,he and the distinguished philosopher Hilary Putnam addressed algorithmically the satisfiability problem for formulae in conjunctive normal form. Martin also cultivated, for a long time, a keen interest in the history and philosophy of computing:in 1965 he collected an anthology on The Undecidable, later on he wrote landmark essays on Church, Gödel, Post, and Turing. Martin Davis and his publications have exerted a wide influence. This book testifies to this influence by focusing on scientific achievements in which he was involved in the first person and on further achievements, studies, and reflections in which work and vision consonant with his have played a role. The editors have collected testimonies of Davis’s contributions to computability, computational logic, and mathematical foundations. The contributions in this volume touch most of the aspects of Davis’s work as seen through the eyes of researchers active in the respective areas. Together, they provide an accurate historical recollection of Davis’s role in advancing our understanding of the connections between logic, computing, and unsolvability. Some contributions are projected into the future, and discuss issues such as contemporary satisfiability solvers, essential unification, quantum computing, and generalizations of Hilbert’s tenth problem. The book is enriched by the inclusion of two historical papers—which had remained unpublished so far—where Davis and Putnam investigate the decidable and the undecidable side of Logic.