JCSS, Volume 20

Volume 20, Number 1, February 1980

Takumi Kasai, Akeo Adachi: A Characterization of Time Complexity by Simple Loop Programs. 1-17
William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. 18-31
Janusz A. Brzozowski, Faith E. Fich: Languages of R-Trivial Monoids. 32-49
John Gallant, David Maier, James A. Storer: On Finding Minimal Length Superstrings. 50-58
Satoru Miyano: One-Way Weak-Stack-Counter Automata. 59-76
Teofilo F. Gonzalez, Joseph JáJá: On the Complexity of Computing Bilinear Forms with {0, 1} Constants. 77-95
Matthew Hennessy: A Proof System for the First-Order Relational Calculus. 96-110
Paul F. Dietz, S. Rao Kosaraju: Recognition of Topological Equivalence of Patterns by Array Automata. 111-116

Selected Papers from STOC 1978

Martin Tompa: Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits. 118-132 , Corrigendum JCSS 23(1): 106 (1981)
Andrea S. LaPaugh, Ronald L. Rivest: The Subgraph Homeomorphism Problem. 133-149
Joost Engelfriet, Grzegorz Rozenberg, Giora Slutzki: Tree Transducers, L Systems, and Two-Way Machines. 150-202
Raymond E. Miller, Chee-Keng Yap: On Formulating Simultaneity for Studying Parallelism and Synchronization. 203-218
John M. Lewis, Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. 219-230
Vaughan R. Pratt: A Near-Optimal Method for Reasoning about Action. 231-254
I. S. Filotti: An Algorithm for Imbedding Cubic Graphs in the Torus. 255-276

A. Ginzburg, Michael Yoeli: Vector Addition Systems and Regular Languages. 277-284
Luc Boasson, Maurice Nivat: Adherences of Languages. 285-309
Jan Paredaens: The Interaction of Integrity Constraints in an Information System. 310-329
Michael A. Arbib, Ernest G. Manes: Foundations of System Theory: The Hankel Matrix. 330-378
Karel Culik II, Arto Salomaa: Test Sets and Checking Words for Homomorphism Equivalence. 379-395
Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, Joel Spencer: Coping with Errors in Binary Search Procedures. 396-404