On datalog vs polynomial time

Foto Afrati; Stavros S. Cosmadakis; Mihalis Yannakakis

doi:10.1006/jcss.1995.1060

Journal of Computer and System Sciences

Paper

01 Jan 1995

On datalog vs polynomial time

View publication

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.

Paper

Classification with nonmetric distances: Image retrieval and class representation

David W. Jacobs, Daphna Weinshall, et al.

IEEE Transactions on Pattern Analysis and Machine Intelligence

Conference paper

Surface light-induced changes in thin polymer films

Andrew Skumanich

SPIE Optics Quebec 1993

Paper

Conditional generative models for learning stochastic processes

Salvatore Certo, Anh Pham, et al.

Quantum Machine Intelligence

Conference paper

Optimization of real phase-mask performance

F.M. Schellenberg, M. Levenson, et al.

BACUS Symposium on Photomask Technology and Management 1991

View all publications

Abstract

Related

Classification with nonmetric distances: Image retrieval and class representation

Surface light-induced changes in thin polymer films

Conditional generative models for learning stochastic processes

Optimization of real phase-mask performance