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

Convergence properties of multi-dimensional stack filters

Peter Wendt

Electronic Imaging: Advanced Devices and Systems 1990

Paper

Irredundancy in circular arc graphs

Martin Charles Golumbic, Renu C. Laskar

Discrete Applied Mathematics

Paper

Output distribution of the burrows-wheeler transform

Karthik Visweswariah, Sanjeev Kulkarni, et al.

IEEE International Symposium on Information Theory - Proceedings

Conference paper

Changes of T_c under epitaxial strain: Implications for the mechanism of superconductivity

J.P. Locquet, J. Perret, et al.

SPIE Optical Science, Engineering, and Instrumentation 1998

View all publications

Abstract

Related

Convergence properties of multi-dimensional stack filters

Irredundancy in circular arc graphs

Output distribution of the burrows-wheeler transform

Changes of Tc under epitaxial strain: Implications for the mechanism of superconductivity

Changes of T_c under epitaxial strain: Implications for the mechanism of superconductivity