Information Processing Letters, Volume 33

Volume 33, Number 1, 27 October 1989

Zoltán Fülöp, Sándor Vágvölgyi: Top-Down Tree Transducers with Deterministic Top-Down Look-Ahead. 3-5
S. J. Wan, S. K. Michael Wong: An Adaptive Algorithm for Finding a Covering Hypersphere. 7-10
De-Lei Lee: On Access and Alignment of Data in a Parallel Processor. 11-14
Mila E. Majster-Cederbaum: The Contraction Property is Sufficient to Guarantee the Uniqueness of Fixed Points of Endofunctors in a Category of Complete Metric Spaces. 15-19
Jayadev Misra: A Simple Proof of a Simple Consensus Algorithm. 21-24
Gadi Taubenfeld: Leader Election in the Presence of n-1 Initial Failures. 25-28
A. Srinivasa Rao, C. Pandu Rangan: Linear Algorithm for Domatic Number Problem on Interval Graphs. 29-33
Bhaskar DasGupta, C. E. Veni Madhavan: An Approximate Algorithm for the Minimal Vertex Nested Polygon Problem. 35-44
Kam-Fai Wong: Comments on ``A Comparison of Concatenated and Superimposed Code Word Surrogate Files for Very Large Data/Knowledge Bases''. 45-52
Michel Raynal: Prime Numbers as a Tool to Design Distributed Algorithms. 53-58

David Avis, J. M. Robert, Rephael Wenger: Lower Bounds for Line Stabbing. 59-62
Christian Buchta: On the Average Number of Maxima in a Set of Vectors. 63-65
Kuo-Liang Chung, Wen-Chin Chen, Ferng-Ching Lin: Fast Computation of Periodic Continued Fractions. 67-72
Andrzej Szepietowski: Some Remarks on the Alternating Hierarchy and Closure Under Complement for Sublogarithmic Space. 73-78
Winfried Thome, Reinhard Wilhelm: Simulating Circular Attribute Grammars Through Attribute Reevaluation. 79-81
Martin Dietzfelbinger: The Speed of Copying on One-Tape Off-Line Turing Machines. 83-89
Alejandro A. Schäffer: Optimal Node Ranking of Trees in Linear Time. 91-96
Stefano Ceri, Georg Gottlob, Letizia Tanca, Gio Wiederhold: Magic Semi-Joins. 97-107
Andrzej Szepietowski: Some Notes on Strong and Weak log log n Space Complexity. 109-112

Roberto Grossi, Fabrizio Luccio: Simple and Efficient String Matching with k Mismatches. 113-120
Takayoshi Shoudai: The Lexicographically First Topological Order Problem is NLOG-Complete. 121-124
Lanfranco Lopriore: Software-Controlled Cache Coherence Protocol for Multicache Systems. 125-130
E. Robert McCurley: Auxiliary Variables in Partial Correctness Programming Logics. 131-133
Selim G. Akl, David Gries, Ivan Stojmenovic: An Optimal Parallel Algorithm for Generating Combinations. 135-139
Ronald V. Book, Shouwen Tang: A Note on Sparse Sets and the Polynomial-Time Hierarchy. 141-143
Ravi B. Boppana: The Average-Case Parallel Complexity of Sorting. 145-146
A. Srinivasa Rao, C. Pandu Rangan: Optimal Parallel Algorithms on Circular-Arc Graphs. 147-156
Bruce Parker, Ian Parberry: Constructing Sorting Networks from k-Sorters. 157-162
Rudolf Berghammer, Gunther Schmidt, Hans Zierer: Symmetric Quotients and Domain Constructions. 163-168

John Hershberger: Finding the Upper Envelope of n Line Segments in O(n log n) Time. 169-174
D. T. Lee, Franco P. Preparata: Parallel Batched Planar Point Location on the CCC. 175-179
Torben Hagerup, Christine Rüb: Optimal Merging and Sorting on the Erew Pram. 181-185
Christos Levcopoulos, Ola Petersson: A Note on Adaptive Parallel Sorting. 187-191
Egon Wanke, Manfred Wiegers: Undecidability of the Bandwidth Problem on Linear Graph Languages. 193-197
José D. P. Rolim: On the Polynomial IO-Complexity. 199-204
Jayaramaiah Boreddy, R. N. Mukherjee: An Algorithm to Find Polygon Similarity. 105-206
Richard Zippel: An Explicit Separation of Relativised Random Polynomial Time and Relativised Deterministic Polynomial Time. 207-212
Janez Zerovnik: A Randomised Heuristical Algorithm for Estimating the Chromatic Number of a Graph. 213-219

Pierluigi Crescenzi, Riccardo Silvestri: Relative Complexity of Evaluating the Optimum Cost and Constructing the Optimum for Maximization Problems. 221-226
Hitoshi Suzuki, Naomi Takahashi, Takao Nishizeki: A Linear Algorithm for Bipartition of Biconnected Graphs. 227-231
Yijie Han, Yoshihide Igarashi: Time Lower Bounds for Sorting on Multi-Dimensional Mesh-Connected Processor Arrays. 233-238
Jürgen Kämper: A Result Relating Disjunctive Self-Reducibility to P-Immunity. 239-242
C. S. Kannan, Henry Y. H. Chuang: Fast Hough Transform on a Mesh Connected Processor Array. 243-248
Laurence Boxer, Russ Miller: Common Intersections of Polygons. 249-254 , Corrigenda: IPL 35(1): 53 (1990)
Divyakant Agrawal, Amr El Abbadi: Exploiting Logical Structures in Replicated Databases. 255-260
Victor Shoup: On the Deterministic Complexity of Factoring Polynomials over Finite Fields. 261-267
Richard J. Anderson, Gary L. Miller: A Simple Randomized Parallel Algorithm for List-Ranking. 269-273

Alan A. Bertossi, Sabrina Moretti: Parallel Algorithms on Circular-Arc Graphs. 275-281
Michael B. Dillencourt: Realizability of Delaunay Triangulations. 283-287
Neil J. Gunther, John G. Shaw: Path Integral Evaluation of Aloha Network Transients. 289-295
Tom Altman, Bogdan S. Chlebus: Sorting Roughly Sorted Sequences in Parallel. 297-300
Stephan Olariu: A Generalization of Chvátal's Star-Cutset Lemma. 301-303
Torben Hagerup, Christine Rüb: A Guided Tour of Chernoff Bounds. 305-308
Zvi Galil, Kunsoo Park: A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming. 309-311
Philip Hingston, Ross Wilkinson: A Distributed Join Algorithm. 313-317
Samir Khuller, Joseph S. B. Mitchell: On a Triangle Counting Problem. 319-321
Edgar Knapp: A Predicate Transformer for Progress. 323-330