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

Volume 22, Number 2, April 1981

• 
  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

Volume 22, Number 3, June 1981

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