JCSS, Volume 22

Volume 22, Number 1, February 1981

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

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

Selected Papers from FOCS 1979

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