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.

Conference paper

Growth and transport properties of multilayer superconducting films of Nd_1.83Ce_0.17CuO_x / YBa₂Cu₃O_7-δ

A. Gupta, R. Gross, et al.

SPIE Advances in Semiconductors and Superconductors 1990

Paper

Multi-dimensional Filter Banks and Wavelets - A System Theoretic Perspective

Sankar Basu

Journal of the Franklin Institute

Paper

Best L¹ approximation by weak chebyshev systems and the uniqueness of interpolating perfect splines

Charles A Micchelli

Journal of Approximation Theory

Paper

Subspace iterative methods for eigenvalue problems

Tong Zhang, G.H. Golub, et al.

Linear Algebra and Its Applications

View all publications

Abstract

Related

Growth and transport properties of multilayer superconducting films of Nd1.83Ce0.17CuOx / YBa2Cu3O7-δ

Multi-dimensional Filter Banks and Wavelets - A System Theoretic Perspective

Best L1 approximation by weak chebyshev systems and the uniqueness of interpolating perfect splines

Subspace iterative methods for eigenvalue problems

Growth and transport properties of multilayer superconducting films of Nd_1.83Ce_0.17CuO_x / YBa₂Cu₃O_7-δ

Best L¹ approximation by weak chebyshev systems and the uniqueness of interpolating perfect splines