David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
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
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Conference paper
Generative Adversarial Symmetry Discovery
Jianke Yang, Robin Walters, et al.
ICML 2023
John A. Hoffnagle, William D. Hinsberg, et al.
Microlithography 2003