see the original item page
in the repository's web site and access all digital files if the item*
share




1995 (EN)
On datalog vs polynomial time (EN)

Yannakakis, M (EN)
Cosmadakis, SS (EN)
Afrati, F (EN)

N/A (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

Lower Bound (EN)
Datalog (EN)
Theorem proving (EN)
Monotonic polynomial time queries (EN)
Recursive functions (EN)
Pumping lemma (EN)
Constraint theory (EN)
Polynomials (EN)
Computational complexity (EN)
Polynomial Time (EN)
Query languages (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

Journal of Computer and System Sciences (EN)

1995


ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS (EN)



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