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

On Seeing Spaghetti: Self-Adjusting Piecewise Toroidal Recognition of Flexible Extruded Objects

John R. Kender, Rick Kjeldsen

IEEE Transactions on Pattern Analysis and Machine Intelligence

Paper

Neural network based iterative learning control for product qualities in batch processes

Zhihua Xiong, Yixin Xu, et al.

International Journal of Modelling, Identification and Control

Conference paper

Anomalous interface degradation of a-Si:H TFTs during LCD lifetime

Frank R. Libsch, Takatoshi Tsujimura

Active Matrix Liquid Crystal Displays Technology and Applications 1997

Paper

Stabilizer-based symmetry breaking constraints for mathematical programs

Leo Liberti, James Ostrowski

Journal of Global Optimization

View all publications

Abstract

Related

On Seeing Spaghetti: Self-Adjusting Piecewise Toroidal Recognition of Flexible Extruded Objects

Neural network based iterative learning control for product qualities in batch processes

Anomalous interface degradation of a-Si:H TFTs during LCD lifetime

Stabilizer-based symmetry breaking constraints for mathematical programs