Logic Programming and Parallel Complexity.

@inproceedings{DBLP:conf/icdt/Kanellakis86,
  author    = {Paris C. Kanellakis},
  editor    = {Giorgio Ausiello and
               Paolo Atzeni},
  title     = {Logic Programming and Parallel Complexity},
  booktitle = {ICDT'86, International Conference on Database Theory, Rome, Italy,
               September 8-10, 1986, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {243},
  year      = {1986},
  isbn      = {3-540-17187-8},
  pages     = {1-30},
  ee        = {db/conf/icdt/Kanellakis86.html},
  crossref  = {DBLP:conf/icdt/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[2]

...

[3]

Mikhail J. Atallah, Susanne E. Hambrusch: Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version). FOCS 1985: 222-231 BibTeX

[4]

Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX

[5]

...

[6]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX

[7]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[8]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[9]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[10]

...

[11]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX

[12]

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX

[13]

...

[14]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX

[15]

W. F. Clocksin, Chris Mellish: Programming in Prolog. Springer 1981
BibTeX

[16]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[17]

Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316(1974) BibTeX

[18]

Stephen A. Cook: A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1-3): 2-21(1985) BibTeX

[19]

Richard Cole, Uzi Vishkin: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. STOC 1986: 206-219 BibTeX

[20]

Don Coppersmith, Shmuel Winograd: On the Asymptotic Complexity of Matrix Multiplication. SIAM J. Comput. 11(3): 472-492(1982) BibTeX

[21]

Michel de Rougemont: Uniform Definability on Finite Structures with Successor. STOC 1984: 409-417 BibTeX

[22]

Cynthia Dwork, Paris C. Kanellakis, John C. Mitchell: On the Sequential Nature of Unification. J. Log. Program. 1(1): 35-50(1984) BibTeX

[23]

Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. CADE 1986: 416-430 BibTeX

[24]

Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX

[25]

...

[26]

...

[27]

Steven Fortune, James Wyllie: Parallelism in Random Access Machines. STOC 1978: 114-118 BibTeX

[28]

...

[29]

...

[30]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[31]

...

[32]

Yuri Gurevich, Saharon Shelah: Fixed-Point Extensions of First-Order Logic. FOCS 1985: 346-353 BibTeX

[33]

Yuri Gurevich: Algebras of Feasible Functions. FOCS 1983: 210-214 BibTeX

[34]

Yuri Gurevich, Harry R. Lewis: A Logic for Constant-Depth Circuits. Information and Control 61(1): 65-74(1984) BibTeX

[35]

David Harel, Dexter Kozen: A Programming Language for the Inductive Sets, and Applications. Information and Control 63(1/2): 118-139(1984) BibTeX

[36]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[37]

John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX

[38]

...

[39]

Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981) BibTeX

[40]

Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX

[41]

Neil Immerman: Languages Which Capture Complexity Classes (Preliminary Report). STOC 1983: 347-354 BibTeX

[42]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[43]

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX

[44]

Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117(1976) BibTeX

[45]

...

[46]

...

[47]

Dexter Kozen: Complexity of Finitely Presented Algebras. STOC 1977: 164-177 BibTeX

[48]

...

[49]

Richard M. Karp, Eli Upfal, Avi Wigderson: Constructing a Perfect Matching is in Random NC. STOC 1985: 22-32 BibTeX

[50]

Robert A. Kowalski: Predicate Logic as Programming Language. IFIP Congress 1974: 569-574 BibTeX

[51]

...

[52]

Jan Maluszynski, Henryk Jan Komorowski: Unification-Free Execution of Logic Programs. SLP 1985: 78-86 BibTeX

[53]

Alberto Martelli, Ugo Montanari: An Efficient Unification Algorithm. ACM Trans. Program. Lang. Syst. 4(2): 258-282(1982) BibTeX

[54]

Gary L. Miller, John H. Reif: Parallel Tree Contraction and Its Application. FOCS 1985: 478-489 BibTeX

[55]

Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) BibTeX

[56]

...

[57]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 BibTeX

[58]

...

[59]

Nicholas Pippenger: On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311 BibTeX

[60]

Mike Paterson, Mark N. Wegman: Linear Unification. J. Comput. Syst. Sci. 16(2): 158-167(1978) BibTeX

[61]

...

[62]

John H. Reif: An Optimal Parallel Algorithm for Integer Sorting. FOCS 1985: 496-504 BibTeX

[63]

John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX

[64]

...

[65]

Walter L. Ruzzo: Tree-Size Bounded Alternation. J. Comput. Syst. Sci. 21(2): 218-235(1980) BibTeX

[66]

Walter L. Ruzzo: On Uniform Circuit Complexity. J. Comput. Syst. Sci. 22(3): 365-383(1981) BibTeX

[67]

Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 BibTeX

[68]

Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX

[69]

...

[70]

Vladimir Yu. Sazonov: A Logical Approach to the Problem "P=NP?". MFCS 1980: 562-575 BibTeX

[71]

Jacob T. Schwartz: Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27(4): 701-717(1980) BibTeX

[72]

...

[73]

Robert Endre Tarjan, Uzi Vishkin: Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary). FOCS 1984: 12-20 BibTeX

[74]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[75]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[76]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX

[77]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[78]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX

[79]

...

[80]

...

[81]

Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

[82]

Uzi Vishkin: Randomized Speed-Ups in Parallel Computation. STOC 1984: 230-239 BibTeX

[83]

...

[84]

Jeffrey Scott Vitter, Roger A. Simons: New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P. IEEE Trans. Computers 35(5): 403-418(1986) BibTeX

[85]

Leslie G. Valiant, Sven Skyum, S. Berkowitz, Charles Rackoff: Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput. 12(4): 641-644(1983) BibTeX

[86]

Hiroto Yasuura: On Parallel Computational Complexity of Unification. FGCS 1984: 235-243 BibTeX

[87]

...

Referenced by

1. Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251
2. Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142
3. Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336
4. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
5. Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236
6. Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348