Information Processing Letters, Volume 13

Volume 13, Number 1, 27 October 1981

Osamu Watanabe: A Fast Algorithm for Finding all Shortest Paths. 1-3
Gilbert N. Lewis, Nancy J. Boynton, F. Warren Burton: Expected Complexity of Fast Search with Uniformly Distributed Data. 4-7
James A. Storer: Constructing Full Spanning Trees for Cubic Graphs. 8-11
Oscar H. Ibarra, Shlomo Moran: Deterministic and Probabilistic Algorithms for Maximum Bipartite Matching Via Fast Matrix Multiplication. 12-15
James F. Korsh: Greedy Binary Search Trees are Nearly Optimal. 16-19
Ashok K. Agrawala, Satish K. Tripathi: On the Optimality of Semidynamic Routing Schemes. 20-22
Kotagiri Ramamohanarao, Ron Sacks-Davis: Hardware Address Translation for Machines with a Large Virtual Memory. 23-29
Géraud Sénizergues: A New Class of C.F.L. for Which the Equivalence is Decidable. 30-34
Hamish I. E. Gunn, David M. Harland: Degrees of Constancy in Programming Languages. 35-38
Yu. G. Stoyan, S. V. Smelyakov: An Approach to the Problems of Routing Optimization in the Regions of Intricate Shape. 39-43

Volume 13, Number 2, 13 November 1981

Mireille Clerbout, Michel Latteux: The Inclusion of D0L in MULTI-RESET. 45-47
O. M. Makarov: Using Duality for the Synthesis of an Optimal Algorithm Involving Matrix Multiplication. 48-49
Robert Hood, Robert Melville: Real-Time Queue Operation in Pure LISP. 50-54
Mikhail J. Atallah, S. Rao Kosaraju: An Adversary-Based Lower Bound for Sorting. 55-57
Wojciech Rytter: The Dynamic Simulation of Recursive and Stack Manipulation Programs. 58-63
Mireille Régnier: On the Average Height of Trees in Digital Search and Dynamic Hashing. 64-66
Ysmar V. Silva Filho: Optimal Choice of Discriminators in a Balanced k-d Binary Search Tree. 67-70
Victor Y. Pan: The Lower Bounds on the Additive Complexity of Bilinear Problems in Terms of Some Algebraic Quantities. 71-72
Ronald V. Book: NTS Grammars and Church-Rosser Systems. 73-76
Jeffrey Scott Vitter: A Shared-Memory Scheme for Coalesced Hashing. 77-79
Akira Nakamura: Some Remarks on One-Pebble Rectangular Array Acceptors. 80-84
Shlomo Moran: A Note on `Is Shortest Path Problem not Harder Than Matrix Multiplication?'. 85-86
Francesco Romani: Author's Reply to S. Moran's Note on the Shortest Path Problem. 87

Volume 13, Number 3, 13 December 1981

Oscar H. Ibarra, Louis E. Rosier: On the Decidability of Equivalence for Deterministic Pushdown Transducers. 89-93
Hideki Yamasaki: On Weak Persistency of Petri Nets. 94-97
Tat-hung Chan: Deciding Freeness for Program Schemes with a Single Unary Function. 98-102
R. H. Barlow, D. J. Evans, J. Shanehchi: A Parallel Merging Algorithm. 103-106
Refael Hassin: Maximum Flow in (s, t) Planar Networks. 107
Andrzej Ehrenfeucht, Grzegorz Rozenberg: On the Subword Complexity of D0L Languages with a Constant Distribution. 108-113
Richard S. Bird: The Jogger's Problem. 114-117
M. D. Atkinson: The Cyclic Towers of Hanoi. 118-119
Donald MacDavid Tolle, William E. Siddall: On the Complexity of Vector Computations in Binary Tree Machines. 120-124
Dorothy E. Denning, Henk Meijer, Fred B. Schneider: More on Master Keys for Group Sharing. 125-126
Jan L. A. van de Snepscheut: Synchronous Communication Between Asynchronous Components. 127-130

Volume 13, Number 4/5, 1981

Christos H. Papadimitriou, Mihalis Yannakakis: The Clique Problem for Planar Graphs. 131-133
Gerhard Barth: An Alternative for the Implementation of the Knuth-Morris-Pratt Algorithm. 134-137
R. H. Davis, C. Rinaldi, C. J. Trebilcock: Data Compression in Limited Capacity Microcomputer Systems. 138-141
Wojciech Rytter: Time Complexity of Languages Recognized by One-Way Multihead Pushdown Automata. 142-144
Wojciech Rytter: A Hardest Language Recognized by Two-Way Nondeterministic Pushdown Automata. 145-146
Viktor K. Sabelfeld: Tree Equivalence of Linear Recursive Schemata is Polynomial-Time Decidable. 147-153
Nathan Goodman, Oded Shmueli: Limitations of the Chase. 154-156
Alan A. Bertossi: The Edge Hamiltonian Path Problem is NP-Complete. 157-159
Laurent Siklóssy: Efficient Query Evaluation in Relational Data Bases with Missing Values. 160-163
Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Testing Whether a Graph is a Superconcentrator. 164-167
Jacob T. Schwartz: Finding the Minimum Distance Between Two Convex Polygons. 168-170
Massimo Ancona, Vittoria Gianuzzi: A New Method for Implementing LR(k) Tables. 171-176
Herbert Edelsbrunner, Hermann A. Maurer: On the Intersection of Orthogonal Objects. 177-181
Akira Nakamura, Kunio Aizawa: Acceptors for Isometric Parallel Context-Free Array Languages. 182-186
M. Howard Williams: A Systematic Test for Extended Operator Precedence. 187-190
Hiroto Yasuura: Width and Depth of Combinational Logic Circuits. 191-194
Rusins Freivalds: Projections of Languages Recognizable by Probabilistic and Alternating Finite Multitape Automata. 195-198
R. K. Arora, N. K. Sharma: Guarded Procedure: A Distributed Programming Concept. 199-203
Giovanni Guida, Marco Somalvico: Multi-Problem-Solving: Knowledge Representation and System Architecture. 204-214
Henry S. Warren Jr., A. Shawhan Fox, Peter W. Markstein: Modulus Division on a Two's Complement Machine. 215-217
José M. Troya, A. Vaquero: An Approximation Algorithm for Reducing Expected Head Movement in Linear Storage Devices. 218-220