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

Volume 33, Number 2, 10 November 1989

• 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

Volume 33, Number 3, 30 November 1989

• 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

Volume 33, Number 4, 21 December 1989

• 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

Volume 33, Number 5, 10 January 1990

• 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

Volume 33, Number 6, 10 February 1990

• 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