zhao2024evaluating (582B)
1 # Zhao2024evaluating 2 3 [computational_complexity] of [datalog_semiring_query_evaluation] under [naturally_ordered_semiring] 4 5 - uses [grounding] 6 - has [lower_bounds] but still over a class of programs, not over a specific program 7 - reduction from [clique] 8 9 mentions cases: 10 11 - [chain_datalog], cf [yannakakis1990graph] 12 - connected to [CFGs] / [context_free_reachability] 13 - [cubic] [data_complexity] 14 - chain rules of the form R(x,y) <- P1(x,z1) ... Pn(zn-1,y) 15 16 Up: [academic_paper] on [datalog_semiring_query_evaluation], [datalog_fine_grained] 17 18 See also: [zhao2024evaluatingb]