Transitivity and Equivalence in Decidable Fragments of First-Order Logic
Of all the properties of binary relations encountered in logic, those of transitivity and equivalence are perhaps the most salient. On the other hand, it is well-known that these properties are typically not expressible in fragments of first-order logic for which the satisfiability problem is known to be decidable - most notably, the two-variable fragment and the guarded fragment. The question therefore arises as to what happens to familiar, decidable fragments of first-order logic under the assumption that a specified collection of binary predicates be interpreted as transitive relations or as equivalences. This question has been the subject of intensive study in the past few years, and my talk summarizes the current state of play in this area.
Ian Pratt-Hartmann studied Mathematics and Philosophy at Brasenose College, Oxford, and Philosophy at Princeton and Stanford Universities, gaining his PhD. from Princeton in 1987. He is currently Senior Lecturer in the Department of Computer Science at the University of Manchester. Dr. Pratt-Hartmann's research interests range widely over the fields of computational logic, spatial logic and natural language semantics.
Actions, Processes, and Ontologies
We overview reasoning about actions and processes over ontologies (or knowledge bases) expressed in Description Logics (DLs). This is a critical research challenge that has resisted good, robust solutions for a long time. In particular, while well-developed theories of actions and processes exist in AI, e.g., the ones based on the Situation Calculus, these theories are not well-behaved when applied to DL ontologies, since the latter impose very difficult state constraints. Here we restate this difficulty, by showing that combining even the simplest DLs and the simplest theory of actions in Situation Calculus leads to undecidability of the simplest reasoning task: satisfiability. We then look into a radically different approach, based on so-called Levesque’s functional view of knowledge bases, that has been proved quite fruitful lately. This approach sees the knowledge base (or ontology) as a system that allows for two kinds of operations: ASK, which returns the (certain) answer to queries, and TELL, which produces a new knowledge base as the result of the application of an atomic action (also related to update). In particular we show that under this view even verification of sophisticated dynamic properties (e.g., formulated in first-order variants of mu-calculus) over ontologies expressed in DLs, ranging from light-weight to very expressive ones, becomes decidable under interesting general conditions.
Giuseppe De Giacomo is a professor at Sapienza Universita' di Roma. He has contributed to diverse areas of AI and CS. In the mid 90's, he explored the correspondence between Description Logics and Logics of Programs, and devised results and reasoning techniques for expressive Description Logics, which contributed to the birth of OWL and OWL2. At the end of the 90', together with his group in Rome, he started the research on conjunctive query answering in Description Logics. He is one of the developers of the DL-Lite family of Description Logics, which have been recently shaping the area of Ontology-Based Data Access. In Databases, he did foundational work on data modeling, data integration, and view based query processing with regular path queries, for both semi-structured and graph data. He has always had a deep interest for Reasoning about Actions and Processes. He profoundly influenced the definition of ConGolog and its successor IndiGolog, which are among the best known formalism for expressing high-level robot programs. He devised one of the best known formal approaches for service composition, the so-called ``Roman Model'', which has been further developed in AI for behavior compositions synthesis of devices and agents. Recently, he provided foundational results on artifact-based business processes, showing the decidability of verification and synthesis in infinite state data-aware systems.
Drugs, Genetics and Phenotypes: an Admission of Formal Semantics in Biomedical Research
With its focus on investigating the nature and basis for the sustained existence of living systems, modern biology has always been a fertile, if not challenging, domain for formal knowledge representation and automated reasoning. Over the past 15 years, hundreds of projects have developed or leveraged ontologies for entity recognition and relation extraction, semantic annotation, data integration, query answering, consistency checking, association mining and other forms of knowledge discovery. In this talk, I will discuss our efforts to build a rich foundational network of ontology-annotated linked data, discover significant biological associations across these data using a set of partially overlapping ontologies, and identify new avenues for drug discovery by applying measures of semantic similarity over phenotypic descriptions. As the portfolio of Semantic Web technologies continue to mature in terms of functionality, scalability and an understanding of how to maximize their value, increasing numbers of biomedical researchers will be strategically poised to pursue increasingly sophisticated KR projects aimed at improving our overall understanding of the capability and behaviour of biological systems.
Dr. Michel Dumontier, PhD is an Associate Professor of Bioinformatics in the Department of Biology, the Institute of Biochemistry and School of Computer Science at Carleton University in Ottawa, Canada. His research focuses on the development of computational methods to increase our understanding of how living systems respond to chemical agents. At the core of the research program is the development and use of Semantic Web technologies to formally represent and reason about data and services so as (1) to facilitate the publishing, sharing and discovery of scientific knowledge produced by individuals and small collectives, (2) to enable the formulation and evaluation scientific hypotheses using our collective tools and knowledge and (3) to create and make available computational methods to investigate the structure, function and behaviour of living systems. Dr. Dumontier serves as a co-chair for the World Wide Web Consortium Semantic Web in Health Care and Life Sciences Interest Group (W3C HCLSIG) and is the Scientific Director for Bio2RDF, a widely used open-source project to create and provide linked data for life sciences.