%0 Conference Paper %1 Funk2022-sw %A Funk, Maurice %A Jung, Jean Christoph %A Lutz, Carsten %B Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence %C California %D 2022 %I International Joint Conferences on Artificial Intelligence Organization %K %T Frontiers and exact learning of ELI queries under DL-Lite ontologies %X We study ELI queries (ELIQs) in the presence of ontologies formulated in the description logic DL-Lite. For the dialect DL-LiteH, we show that ELIQs have a frontier (set of least general generalizations) that is of polynomial size and can be computed in polynomial time. In the dialect DL-LiteF, in contrast, frontiers may be infinite. We identify a natural syntactic restriction that enables the same positive results as for DL-LiteH. We use our results on frontiers to show that ELIQs are learnable in polynomial time in the presence of a DL-LiteH / restricted DL-LiteF ontology in Angluin's framework of exact learning with only membership queries.

@inproceedings{Funk2022-sw, abstract = {We study ELI queries (ELIQs) in the presence of ontologies formulated in the description logic DL-Lite. For the dialect DL-LiteH, we show that ELIQs have a frontier (set of least general generalizations) that is of polynomial size and can be computed in polynomial time. In the dialect DL-LiteF, in contrast, frontiers may be infinite. We identify a natural syntactic restriction that enables the same positive results as for DL-LiteH. We use our results on frontiers to show that ELIQs are learnable in polynomial time in the presence of a DL-LiteH / restricted DL-LiteF ontology in Angluin's framework of exact learning with only membership queries.}, added-at = {2024-09-10T11:56:37.000+0200}, address = {California}, author = {Funk, Maurice and Jung, Jean Christoph and Lutz, Carsten}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2bf51a6f3930411f703fabca464de0645/scadsfct}, booktitle = {Proceedings of the {Thirty-First} International Joint Conference on Artificial Intelligence}, conference = {Thirty-First International Joint Conference on Artificial Intelligence \{IJCAI-22\}}, interhash = {618148050d65dca9154d48c97d2d475c}, intrahash = {bf51a6f3930411f703fabca464de0645}, keywords = {}, location = {Vienna, Austria}, month = jul, publisher = {International Joint Conferences on Artificial Intelligence Organization}, timestamp = {2024-09-10T15:15:57.000+0200}, title = {Frontiers and exact learning of {ELI} queries under {DL-Lite} ontologies}, year = 2022 }