JCSS, Volume 22

Volume 22, Number 1, February 1981

Shlomo Moran: Some Results on Relativized Deterministic and Nondeterministic Time Hierarchies. 1-8
Tsuyoshi Nakamura: Regularity and Firing Sequences of Computation Graphs. 9-28
Stephen J. Willson: Growth Patterns of Ordered Cellular Automata. 29-41
Keijo Ruohonen: The Decidability of the D0L-DT0L Equivalence Problem. 42-52
Paul Chew, Michael Machtey: A Note on Structure and Looking Back Applied to the Complexity of Computable Functions. 53-59
Tatsuo Ohtsuki, Hajimu Mori, Toshinobu Kashiwabara, Toshio Fujisawa: On Minimal Augmentation of a Graph to Obtain an Interval Graph. 60-97
Robert Melville: An Improved Simulation Result for Ink-Bounded Turing Machines. 98-105

Gregory A. Riccardi: The Independence of Control Structures in Abstract Programming Systems. 107-143
Dirk Janssens, Grzegorz Rozenberg: Decision Problems for Node Label Controlled Graph Grammars. 144-177
David A. Workman: SR(s, k) Parsers: A Class of Shift-Reduce Bounded-Context Parsers. 178-197
Michael P. Georgeff: Interdependent Translation Schemes. 198-219
Eitan M. Gurari, Oscar H. Ibarra: The Complexity of Decision Problems for Finite-Turn Multicounter Machines. 220-229
John E. Savage: Area-Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models. 230-242
Theodore P. Baker: Extending Lookahead for LR Parsers. 243-259

Selected Papers from FOCS 1979

Mark N. Wegman, Larry Carter: New Hash Functions and Their Use in Authentication and Set Equality. 265-279
Gilles Brassard: A Time-Luck Tradeoff in Relativized Cryptography. 280-311
Wolfgang J. Paul, Rüdiger Reischuk: On Time versus Space II. (Turing Machines). 312-327
Dexter Kozen: Semantics of Probabilistic Programs. 328-350
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa: A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. 351-364
Walter L. Ruzzo: On Uniform Circuit Complexity. 365-383
Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. 384-406
Ofer Gabber, Zvi Galil: Explicit Constructions of Linear-Sized Superconcentrators. 407-420
Janos Simon: Division in Idealized Unit Cost RAMS. 421-441
Michael Machtey, Paul Young: Remarks on Recursion versus Diagonalization and Exponentially Difficult Problems. 442-453
Nicholas Pippenger: Computational Complexity of Algebraic Functions. 454-470 , -> Correction JCSS 37(3): 395-399 (1988)