Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ
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
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
Conference paper
Distilling common randomness from bipartite quantum states
Igor Devetak, Andreas Winter
ISIT 2003
Conference paper
Optimization of real phase-mask performance
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991