Discrete mathematics

Probably approximately correct learning

Undecidable problem

Hierarchy

Mathematics

Computational learning theory

EXPTIME

Description logic

Algorithm

Decidability

Logic programming

Artificial intelligence

Horn clause

PSPACE

Economics

Computational complexity theory

Programming language

Polynomial hierarchy

Extension (predicate logic)

Computer science

Unsupervised learning

Theoretical computer science

Market economy

Complexity class

Learning 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 and provide 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 conjunctive queries. We exploit this to determine the combined complexity (between ExpTime and NExpTime) and data complexity (second level of the polynomial hierarchy) of separability. For the Horn DL EL, separability is ExpTime-complete both in combined and in data complexity while for its modest extension ELI it is even undecidable. Separability is also undecidable when the KB is formulated in ALC and the separating concept is required to be in EL or ELI.

Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?