Information Processing Letters, Volume 37

Volume 37, Number 1, 10 January 1991

Chung-Kuo Chang, Mohamed G. Gouda: On the Minimum Requirements for Independent Recovery in Distributed Systems. 1-7
Xubo Zhang: Overlap Closures do not Suffice for Termination of General Term Rewriting Systems. 9-11
Soma Chaudhuri, Richard E. Ladner: Safety and Liveness of omega-Context-Free Languages. 13-20
Stephan Olariu: An Optimal Greedy Heuristic to Color Interval Graphs. 21-25
Viggo Kann: Maximum Bounded 3-Dimensional Matching in MAX SNP-Complete. 27-35
Yannis Manolopoulos, Athena Vakali: Seek Distances in Disks with Two Independent Heads Per Surface. 37-42
U. K. Sarkar, P. P. Chakrabarti, Sujoy Ghose, S. C. De Sarkar: Multiple Stack Branch and Bound. 43-48
Douglas M. Campbell, John Higgins: Minimal Visibility Graphs. 49-53
Bin Yu, Xinggang Lin, Youshou Wu: The Tree Representation of the Graph Used in Binary Image Processing. 55-59

Igor Litovsky: Prefix-Free Languages as omega-Generators. 61-65
Fabrizio Luccio, Andrea Pietracaprina, Geppino Pucci: Analysis of Parallel Uniform Hashing. 67-69
Timothy Law Snyder: Lower Bounds for Rectilinear Steiner Trees in Bounded Space. 71-74 , Corrigendum: Inf. Process. Lett. 38(5): 279(1991)
C. C. Handley: A Space Efficient Distributive Sort. 75-78
Roberto Tamassia: An Incremental Reconstruction Method for Dynamic Planar Point Location. 79-83
Yoshihiro Tanaka: A Dual Algorithm for the Satisfiability Problem. 85-89
Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: Probabilistic Polynomial Time is Closed under Parity Reductions. 91-94
Joakim von Wright: Program Inversion in the Refinement Calculus. 95-100
Alan Gibbons, Ridha Ziani: The Balanced Binary Tree Technique on Mesh-Connected Computers. 101-109
Xin He: An Efficient Parallel Algorithm for Finding Minimum Weight Matching for Points on a Convex Polygon. 111-116
Svante Carlsson: An Optimal Algorithm for Deleting the Root of a Heap. 117-120

Sven Skyum: A Simple Algorithm for Computing the Smallest Enclosing Circle. 121-125
Jurek Czyzowicz, K. B. Lakshmanan, Andrzej Pelc: Searching with a Forbidden Lie Pattern in Responses. 127-132
Udi Manber, Ricardo A. Baeza-Yates: An Algorithm for String Matching with a Sequence of don't Cares. 133-136
Pavol Duris, Imrich Vrto: Semelectivity is not Sufficient. 137-141
Bin Jiang: Traversing Graphs in a Paging Environment, BFS or DFS? 143-147
Frederic Green: An Oracle Separating \oplus P from PP^PH. 149-153
Augustus J. E. M. Janssen: An Optimization Problem Related to Neural Networks. 155-157
Galen H. Sasaki: The Effect of the Density of States on the Metropolis Algorithm. 159-163
Dung T. Huynh: The Effective Entropies of Some Extensions of Context-Free Languages. 165-169
Wladyslaw M. Turski: On Starvation and Some Related Issues. 171-174
Micha Hofri, Hadas Shachnai: On the Optimality of the Counter Scheme for Dynamic Linear Lists. 175-179

Zhaofang Wen: Parallel Multiple Search. 181-186
David Pokrass Jacobs: Probabilistic Checking of Associativity in Algebras. 187-191
Xiaotie Deng, Sanjeev Mahajan: Server Problems and Resistive Spaces. 193-196
Robert W. Irving: On Approximating the Minimum Independent Dominating Set. 197-200
Xuehou Tan, Tomio Hirata, Yasuyoshi Inagaki: The Intersection Searching Problem for c-Oriented Polygons. 201-204
Cornelis Huizing, Willem P. de Roever: Introduction to Design Choices in the Semantics of Statecharts. 205-213
Uri Zwick: An Extension of Khrapchenko's Theorem. 215-217
Y. Daniel Liang, Chong Jye Rhee, Sudarshan K. Dhall, S. Lakshmivarahan: A New Approach for the Domination Problem on Permutation Graphs. 219-224
Peter F. Corbett, Isaac D. Scherson: A Unified Algorithm for Sorting on Multidimensional Mesh-Connected Processors. 225-231
Maria J. Serna: Approximating Linear Programming is Log-Space Complete for P. 233-236
Helmut Alt, Norbert Blum, Kurt Mehlhorn, Markus Paul: Computing a Maximum Cardinality Matching in a Bipartite Graph in Time O(^1.5 sqrt m/log n). 237-240

Shyan-Ming Yuan: Topological Properties of Supercube. 241-245
James K. Mullin: A Caution on Universal Classes of Hash Functions. 247-256
Danièle Beauquier: An Undecidable Problem About Rational Sets and Contour Words of Polyominoes. 257-263
Anne Kaldewaij, Berry Schoenmakers: The Derivation of a Tighter Bound for Top-Down Skew Heaps. 265-271
Toshiya Itoh: Characterization for a Family of Infinitely Many Irreducible Equally Spaced Polynomials. 273-277
Yasubumi Sakakibara: On Learning from Queries and Counterexamples in the Presence of Noise. 279-284
Gadi Taubenfeld: On the Nonexistence of Resilient Consensus Protocols. 285-289
Quingzhou Wang, Kam-Hoi Cheng: List Scheduling of Parallel Tasks. 291-297

Dirk Taubner: A Note on the Notation of Recursion in Process Algebras. 299-303
Kim-Heng Teo, Tai-Ching Tuan: An Improved Upper Bound on the Number of Intersections Between Two Rectangular Paths. 305-309
Sabri A. Mahmoud: Motion Estimation Based on Modified Fourier Spectrum. 311-313
Olivier Danvy: Semantics-Directed Compilation of Nonlinear Patterns. 315-322
K. Vidyasankar: A Very Simple Construction of 1-Writer Multireader Multivalued Atomic Variable. 323-326
Biing-Feng Wang, Chuen-Liang Chen, Gen-Huey Chen: A Simple Approach to Implementing Multiplication with Small Tables. 327-329
Zvi Galil, Giuseppe F. Italiano: A Note on Set Union with Arbitrary Deunions. 331-335
Myung-Joon Lee, Kwang-Moo Choe: SLR(k) Covering for LR(k) Grammars. 337-347 , Corrigenda: Inf. Process. Lett. 38(5): 281(1991)
R. Srikant, Kamala Krithivasan: Fastest Path Across Constrained Moving Rectilinear Obstacles. 349-353
Nageswara S. V. Rao, Weixiong Zhang: Building Heaps in Parallel. 355-358