On Datalog vs. polynomial time (extended abstract)
- 1 April 1991
- proceedings article
- Published by Association for Computing Machinery (ACM)
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 queriesKeywords
This publication has 13 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Modularity of cycles and paths in graphsJournal of the ACM, 1991
- Inductive pebble games and the expressive power of datalogPublished by Association for Computing Machinery (ACM) ,1989
- Expressiveness of restricted recursive queriesPublished by Association for Computing Machinery (ACM) ,1989
- The monotone circuit complexity of boolean functionsCombinatorica, 1987
- A complexity theory based on Boolean algebraJournal of the ACM, 1985
- The even‐path problem for graphs and digraphsNetworks, 1984
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- Universality of data retrieval languagesPublished by Association for Computing Machinery (ACM) ,1979