Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
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
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI