On datalog vs polynomial time

 
This item is provided by the institution :

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA
see the original item page
in the repository's web site and access all digital files if the item*
share



Semantic enrichment by EKT
Journal part (EN)
Scientific article (EN)
1995 (EN)
On datalog vs polynomial time (EN)
Yannakakis, M (EN)
Cosmadakis, SS (EN)
Afrati, F (EN)
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. (C) 1995 Academic Press, Inc. (EN)
journalArticle (EN)
Lower Bound (EN)
Datalog (EN)
Monotonic polynomial time queries (EN)
Computer Science, Theory & Methods (EN)
Computational complexity (EN)
Theorem proving (EN)
Recursive functions (EN)
Pumping lemma (EN)
Constraint theory (EN)
Computer Science, Hardware & Architecture (EN)
Polynomials (EN)
Polynomial Time (EN)
Query languages (EN)
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Δημοσιεύσεις μελών Δ.Ε.Π. σε περιοδικά
Journal of Computer and System Sciences (EN)
English
1995 (EN)
http://hdl.handle.net/123456789/11597
ISI:A1995RZ74200005 (EN)
177 (EN)
2 (EN)
0022-0000 (EN)
10.1006/jcss.1995.1060 (EN)
51 (EN)
196 (EN)
ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS (EN)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)