Heng Cao, Haifeng Xi, et al.
WSC 2003
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
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985