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

Vibrational overtones in organic thin films: a novel structural probe

A. Skumanich

SPIE OE/LASE 1992

Conference paper

Total Source Mask Optimization: High-capacity, resist modeling, and production-ready mask solution

Moutaz Fakhry, Yuri Granik, et al.

SPIE Photomask Technology + EUV Lithography 2011

Paper

A Formal Treatment of Non-repudiation Protocols

Satoshi Hada

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

Conference paper

Patterning of highly conducting polyaniline films

T. Graham, A. Afzali, et al.

Microlithography 2000

View all publications

Abstract

Related

Vibrational overtones in organic thin films: a novel structural probe

Total Source Mask Optimization: High-capacity, resist modeling, and production-ready mask solution

A Formal Treatment of Non-repudiation Protocols

Patterning of highly conducting polyaniline films