lutz2022complete (661B)
1 # lutz2022complete 2 3 [academic_paper] by [carsten] and [leif] 4 5 Complexity [trichotomy] for [ontology_mediated_query] about [el] class: 6 7 We know that every [OMQ] from (EL,AQ) (or (EL,CQ)) falls into one of the following classes: 8 9 - [AC0] / [FO-rewritable] 10 - [NL] 11 - but there is actually an infinite hierarchy here: every [OMQ] that can be evaluated in NL translates into an equivalent [linear_datalog] program, and for every [datalog_width] k of such a program ([arity] of [IDB_relations]) we find an [OMQ] that actually needs width at least k in the rewriting (equivalently: has [pathwidth] k) 12 - [PTime] 13 14 [Open_question]: extend to [ELI] 15 16 Up: [academic_paper]