Presentation for Final Project - Theory of Computation
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
% Welcome! This is the unofficial University of Udine beamer template.
% See README.md for more informations about this template.
% This style has been developed following the "Manuale di Stile"
% (Style Manual) of the University of Udine. You can find the
% manual here: https://www.uniud.it/it/ateneo-uniud/ateneo-uniud/identita-visiva/manuali-immagine-stile/manuale-stile
% Note: for some reason, the RGB values specified in the manual
% do NOT render correctly in Beamer, so they have been redefined
% for this document using the high level chromo-optic deep neural
% quantistic technology offered by Microsoft Paint's color picker.
% We defined four theme colors: UniBrown, UniBlue, UniGold
% and UniOrange. For example, to write some uniud-brownish
% text, just use: \textcolor{UniBrown}{Hello!}
% Note that [usenames,dvipsnames] is MANDATORY due to compatibility
% issues between tikz and xcolor packages.
\documentclass[usenames,dvipsnames]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{verbatim}
\usetheme{uniud}
\addtobeamertemplate{footnote}{}{\vspace{2ex}}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{color}
%%% Bibliography
\usepackage[style=authoryear,backend=biber]{biblatex}
\addbibresource{bibliography.bib}
%%% Suppress biblatex annoying warning
\usepackage{silence}
\WarningFilter{biblatex}{Patching footnotes failed}
%%% Some useful commands
% pdf-friendly newline in links
\newcommand{\pdfnewline}{\texorpdfstring{\newline}{ }}
% Fill the vertical space in a slide (to put text at the bottom)
\newcommand{\framefill}{\vskip0pt plus 1filll}
\title[Final Project - Theory of Computation]{On the Complexity of Dealing with Inconsistency in Description Logic Ontologies}
\date[May 2017]{May 4, 2017}
\author[Ismael Villanueva-Miranda]{
Riccardo Rosati Universit\'a di Roma, Italy
\pdfnewline
\pdfnewline
Ismael Villanueva-Miranda | Final Project
\pdfnewline
\texttt{ivillanueva5@miners.utep.edu}
}
\institute{Theory of Computation - University of Texas at El Paso}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%OUTLINE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Outline}
\tableofcontents
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%WHAT IS AN ONTOLOGY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What is an ontology?}
\begin{frame}{What is an ontology?}
An ontology {\color{Red}defines a common vocabulary} for researchers who need to {\color{Red}share information} in a domain.
\\
\center EXAMPLE: PIZZA ONTOLOGY
\begin{block}{CONCEPTS}
Pizza, Pizza Base, Pizza Toppings
\end{block}
\begin{block}{PROPERTIES}
hasBase, hasCheeseTopping, hasCheeseTopping, HasPeperonniTopping
\end{block}
\textbf{\textcolor{UniOrange}{Pizza hasBase DeepPanBase and hasCheeseTopping Mozzarella}}
\vskip 0.5cm
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%WHAT IS DESCRIPTION LOGIC?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are Description Logics (DL)?}
\begin{frame}{What are Description Logics (DL)?}
A Description Logics (DL) models concepts, roles and individuals, and their relationships.
\begin{itemize}
\item \textcolor{black}{{\texttt{DL are a family of formal knowledge representation languages.}}}
\item \textcolor{black}{{\texttt{DL are decidable fragments of First Order Logic}}}
\end{itemize}
\includegraphics[width=\linewidth]{graphics/DLpizza}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%WHAT IS AN INCONSISTENCY IN DL?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What is an Inconsistency in DL?}
\begin{frame}{What is an Inconsistency in DL?}
An inconsistency is identified with the existence of unsatisfiable axioms\footnote{Axioms: assertions in a logical form that together comprise the overall theory that the ontology describes in its domain of application.}.
\begin{center}
\fontsize{16}{20}\selectfont{\color{Red} \textbf{ VegetarianPizza}} $\sqsubset$ $\forall$ hasTopping Vegetable
\\
{\color{Red} \textbf{VegetarianPizza}} $\sqsubset$ $\exists$ hasTopping Meat
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%THE PROBLEM: DEALING WITH INCOSISTENCY IN DL
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The problem: Dealing with inconsistency}
\begin{frame}{The problem: Dealing with inconsistency}
\begin{itemize}
\item \textcolor{black}{{\texttt{The size of ontologies used by real applications is scaling up}}}
\item \textcolor{black}{{\texttt{Ontologies are increasingly merged and integrated into larger ontologies}}}
\item \textcolor{black}{{\texttt{The probability of {\color{Red}introducing inconsistency} is consequently {\color{Red}getting higher} }}}
\item \textcolor{black}{{\texttt{Dealing with inconsistency is becoming a practical issue in ontology-based systems}}}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%THE SOLUTION: Alternative Approach
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Solution: Alternative Approach}
\begin{frame}{The Solution: Alternative Approach}
An alternative approach is to define inconsistency-tolerant semantics:
\begin{itemize}
\item \textcolor{black}{{\texttt{are able to derive meaningful conclusions from inconsistent ontologies}}}
\item \textcolor{black}{{\texttt{can be the formal basis for an automated treatment of inconsistency}}}
\item \textcolor{black}{{\texttt{are based on {\color{Red}repairing} (i.e., modifying) the extensional knowledge ({\color{Red}ABox})}}}
\item \textcolor{black}{{\texttt{a {\color{Red}repair} is a {\color{Red}maximal subset of the ABox} that is consistent with the TBox}}}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%THE SOLUTION: Alternative Approach
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Description Logics Considered}
\begin{frame}{The Solution: The DL Considered}
The DLs mainly considered in this paper are the following:
\begin{itemize}
\item \textcolor{black}{{\texttt{EL: A prominent tractable DL}}}
\item \textcolor{black}{{\texttt{ALC: A very well-known DL which correspond to multimodal logic $K_{n}$}}}
\item \textcolor{black}{{\texttt{SHIQ: A very expensive DL which constitutes the basis of the OWL family}}}
\end{itemize}
\begin{center}
\includegraphics[width=\linewidth]{graphics/DLstudied}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%THE SOLUTION: Alternative Approach
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Data Complexity}
\begin{frame}{The Solution: Data Complexity}
In this paper, they consider data complexity (i.e., the complexity with respect to the size of the ABox) and combined complexity (i.e., the complexity with respect to the size of the whole input) of UCQ\footnote{Union of Conjunctive Queries} entailment and instance checking.
\begin{center}
\includegraphics[width=\linewidth]{graphics/DLcomplexity}
\\Table: results on the complexity of instance checking and UCQ entailment under standard semantics in the DLs
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Complexity Results
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Complexity Results}
\begin{frame}{Complexity Results}
Complexity of UCQ entailment over DL KBs under inconsistency-tolerant semantics.
\begin{center}
\includegraphics[width=\linewidth]{graphics/DLresults}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Complexity Results
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}
\begin{frame}{Conclusions}
The authors conclude the following:
\begin{itemize}
\item \textcolor{black}{{\texttt{reasoning under the {\color{Red}approximated semantics} is in general {\color{Red}intractable} even for tractable DLs.}}}
\item \textcolor{black}{{\texttt{reasoning under the {\color{Red}inconsistency-tolerant} semantics is {\color{Red}inherently intractable}, even for very simple DLs.}}}
\end{itemize}
\end{frame}
\end{document}