Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Paper
On datalog vs polynomial time
Abstract
We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a “Pumping Lemma” for Datalog queries. © 1995 by Academic Press, Inc.
Related
Guillaume Buthmann, Tomoya Sakai, et al.
ICASSP 2025
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Conference paper
Compression for data archiving and backup revisited
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009