JCSS, Volume 28

Volume 28, Number 1, February 1984

Special Issue to the Memory of Anthony C. Klug

Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. 3-28
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. 29-59
Nathan Goodman, Oded Shmueli: The Tree Projection Theorem and Relational Query Processing. 60-79
Tomasz Imielinski, Witold Lipski Jr.: The Relational Model of Data and Cylindric Algebras. 80-102
Paris C. Kanellakis, Christos H. Papadimitriou: Is Distributed Locking Harder? 103-120
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. 121-141
Carlo Zaniolo: Database Relations with Null Values. 142-166
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. 167-189

Selected Papers of STOC 1982

Yishai A. Feldman, David Harel: A Probabilistic Dynamic Logic. 193-215
Walter L. Ruzzo, Janos Simon, Martin Tompa: Space-Bounded Hierarchies and Probabilistic Computations. 216-230
Martin Fürer: Data Structures for Distributed Counting. 231-243
Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). 244-259
Christos H. Papadimitriou, Michael Sipser: Communication Complexity. 260-269
Shafi Goldwasser, Silvio Micali: Probabilistic Encryption. 270-299
Sandeep N. Bhatt, Frank Thomson Leighton: A Framework for Solving VLSI Graph Layout Problems. 300-343

Manfred K. Warmuth, David Haussler: On the Complexity of Iterated Shuffle. 345-358
Michael C. Loui: Minimizing Access Pointers into Trees and Arrays. 359-378
Dan E. Willard: New Trie Data Structures Which Support Very Fast Search Operations. 379-394
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Monadic Recursion Schemes: Exponential Time Bounds. 395-419
Errol L. Lloyd, S. S. Ravi: One-Layer Routing without Component Constraints. 420-438
Robin Milner: A Complete Inference System for a Class of Regular Behaviours. 439-466