Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
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
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Conference paper
Neave effect also occurs with Tausworthe sequences
Shu Tezuka
WSC 1991
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences