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 BibTeX
S. J. Wan, S. K. Michael Wong: An Adaptive Algorithm for Finding a Covering Hypersphere. 7-10 BibTeX
De-Lei Lee: On Access and Alignment of Data in a Parallel Processor. 11-14 BibTeX
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 BibTeX
Jayadev Misra: A Simple Proof of a Simple Consensus Algorithm. 21-24 BibTeX
Gadi Taubenfeld: Leader Election in the Presence of n-1 Initial Failures. 25-28 BibTeX
A. Srinivasa Rao, C. Pandu Rangan: Linear Algorithm for Domatic Number Problem on Interval Graphs. 29-33 BibTeX
Bhaskar DasGupta, C. E. Veni Madhavan: An Approximate Algorithm for the Minimal Vertex Nested Polygon Problem. 35-44 BibTeX
Kam-Fai Wong: Comments on ``A Comparison of Concatenated and Superimposed Code Word Surrogate Files for Very Large Data/Knowledge Bases''. 45-52 BibTeX
Michel Raynal: Prime Numbers as a Tool to Design Distributed Algorithms. 53-58 BibTeX

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

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

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

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

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