BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T052509Z
UID:Seminar-ARK-521@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Louwe Kuijer:MAILTO:Louwe.Kuijer@liverpool.ac.uk
DTSTART:20190607T150000
DTEND:20190607T160000
SUMMARY:Argumentation and Representation of Knowledge Series
DESCRIPTION:Hadrien Pulcini: Learning Description Logic Concepts: When Can Positive and Negative Examples be Separated?\n\nLearning description logic (DL) concepts from positive and negative examples given in the form of labeled data items in a KB has received significant attention in the literature. We study the fundamental question of when a separating DL concept exists, providing useful model-theoretic characterizations as well as complexity results for the associated decision problem. For expressive DLs such as ALC and ALCQI, our characterizations show a surprising link to the evaluation of ontology-mediated queries. We exploit this to determine the combined complexity (either ExpTime-complete or NExpTime-complete) and data complexity (sigma_2^p-complete) of separability. We also consider the Horn DLs EL and ELI for which separability is ExpTime (both in combined and in data complexity) and undecidable, respectively. Finally, when the KB is formulated in an expressive DL such as ALC and the separating concept in a Horn DL such as EL, then separability is undecidable.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=521
LOCATION:
END:VEVENT
END:VCALENDAR