Finite entailment of UCRPQs over ALC ontologies

Speaker(s)

Albert Gutowski

Affiliation

MIM UW

Date

June 15, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We solve finite ontology-mediated query entailment for ontologies expressed in ALC (a description logic, closely related to (multi)modal logic) and queries expressed as UCRPQs (extending UCQs - unions of conjunctive queries - with constraints on paths given by regular expressions). We combine a simple but interesting construction for deterministic finite automata with a number of techniques used previously in similar query entailment settings. During this talk, the main focus will be on this construction for DFA and the way we use it in the proof. This is joint work with Víctor Gutiérrez Basulto, Yazmin Ibáñez García, and Filip Murlak.

---