Title: Ontology-based data access: succinctness and complexity
Speaker: Michael Zakharyaschev, professor of computer science at Department of Computer Science and Information Systems, University of London, Birkbeck.
Abstract: Ontology-based data access and management (OBDA) is a popular paradigm of organising access to various types of data sources that has been developed since the mid 2000s. In a nutshell, OBDA separates the user from the data sources (relational databases, triple stores, etc.) by means of an ontology, which provides the user with a convenient query vocabulary, hides the structure of the data sources, enriches incomplete data with background knowledge, and supports queries to multiple and possibly heterogeneous data sources. A key concept of OBDA is first-order rewritability, which reduces the problem of answering ontology-mediated queries (OMQs) to standard database query evaluation.The aim of this talk is to give an introduction to OBDA via query rewriting, discuss its computational costs, and real-world applications. In particular, we consider two fundamental computational problems in OBDA with the W3C standard ontology language OWL 2 QL - the succinctness problem for first-order rewritings, and the complexity problem for OMQ evaluation - and show how these problems are related to classical circuit complexity and database query evaluation.
Title : Data mining problems in computational mass spectrometry
Speaker : Attila Kertesz-Farkas, Associate Professor, Faculty of Computer Science, School of Data Analysis and Artificial Intelligence
Abstract: Tandem mass spectrometry has been extensively used to determine the amino acid sequence of a protein molecule. Amino acids are the building blocks of protein molecules, traditionally, there are 20 of them, and knowing the amino acid sequences of proteins gives us important insight to the function and structure of the protein molecule.A protein first in vitro has been cut into smaller pieces, called peptides, to avoid experimental complexity. A mass spectrometer is then used to measure the mass distribution (spectrum) of the peptide fragments. These spectra, generated, can be considered as fingerprint of the peptide molecule. Computational programs are then applied to identify the amino acid sequence of proteins from mass spectrum data. In this presentation, I will give a general introduction to the computational challenges that scientist faces every day in mass spectrometry data analysis.
Title : A Characterization of the Single-Peaked Domain
Speaker : Prof. Dr. Clemens Puppe, Chair, Economic Theory Karlsruhe Institute of Technology (KIT)
Abstract: It is proved that, among all restricted preference domains that guarantee consistency (i.e. transitivity) of pairwise majority voting, the single-peaked domain is the only minimally rich and connected domain that contains two completely reversed strict preference orders. It is argued that this result explains the predominant role of single-peakedness as a domain restriction in models of political economy and elsewhere over the last seven decades. Several intermediate steps of the proof shed further light on the structure of restricted domains that guarantee transitivity of pairwise majority voting, among them the result that a single-crossing (`order-restricted´) domain can be minimally rich only if it is a subdomain of a single-peaked domain.
Title: "On computing all abductive explanations from a propositional Horn theory"
Speaker: Kazuhisa Makino, Research Institute for Mathematical Sciences (RIMS) at Kyoto University.
Abstract: Abduction is a fundamental mode of reasoning with applications in many areas of AI and Computer Science. The computation of abductive explanations is an important computational problem, which is at the core of early systems such as the ATMS and Clause Management Systems and is intimately related to prime implicate generation in propositional logic. Many algorithms have been devised for computing some abductive explanation, and the complexity of the problem has been well studied. However, little attention has been paid to the problem of computing multiple explanations, and in particular all explanations for an abductive query. We fill this gap and consider the computation of all explanations of an abductive query from a propositional Horn theory, or of a polynomial subset of them. Our study pays particular attention to the form of the query, ranging from a literal to a compound formula, to whether explanations are based on a set of abducible literals and to the representation of the Horn theory, either by a Horn conjunctive normal form (CNF) or model-based in terms of its characteristic models. For these combinations, we present either tractability results in terms of polynomial total-time algorithms, intractability results in terms of nonexistence of such algorithms (unless P = NP), or semi-tractability results in terms of solvability in quasi-polynomial time, established by polynomial-time equivalence to the problem of dualizing a monotone CNF expression. Our results complement previous results in the literature, and refute a longstanding conjecture by Selman and Levesque. They elucidate the complexity of generating all abductive explanations and shed light on related problems such as generating sets of restricted prime implicates of a Horn theory. The algorithms for tractable cases can be readily applied for generating a polynomial subset of explanations in polynomial time.