Information Processing Letters, Volume 22

Volume 22, Number 1, January 1986

P. Chatelin: On Transformations of Algorithms to Multiply 2*2 Matrices. 1-5 BibTeX
Jean Berstel: Every Iterated Morphism Yields a co-CFL. 7-9 BibTeX
Victor Y. Pan: The Trade-Off Between the Additive Complexity and the Asynchronicity of Linear and Bilinear Algorithms. 11-14 BibTeX
Bernd Baumgarten, Peter Ochsenschläger: On Termination and Phase Changes in the Presence of Unreliable Communication. 15-20 BibTeX
Kenneth L. Clarkson: Linear Programming in O(n * (3_d)_2) Time. 21-24 BibTeX
A. Lingus: The Greedy and Delaunay Triangulations are Not Bad in the Average Case. 25-31 BibTeX
Louis E. Rosier: A Note on Presburger Arithmetic with Array Segments, Permutation and Equality. 33-35 BibTeX
Mirko Krivánek: Hexagonal Unit Network a Tool for Proving the NP-Completeness Results of Geometric Problems. 37-41 BibTeX
C. T. M. Jacobs, Peter van Emde Boas: Two Results on Tables. 43-48 BibTeX
Valentinas Kriauciukas: Tree-Like Parse and Polynomial Subclasses of Search Problems. 49-54 BibTeX

Ivan Stojmenovic, Eljas Soisalon-Soininen: A Note on Approximate Convex Hulls. 55-56 BibTeX
Amos Israeli, Yossi Shiloach: An Improved Parallel Algorithm for Maximal Matching. 57-60 BibTeX
Ke-Chang Dai: EDISON-80, a Language for Modular Programming of Parallel Processes. 61-72 BibTeX
Michael D. Grigoriadis, B. Kalantari: A Lower Bound to the Complexity of Euclidean and Rectilinear Matching Algorithms. 73-76 BibTeX
Amos Israeli, Alon Itai: A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. 77-80 BibTeX
Charles U. Martel: Lower Bounds on Parallel Algorithms for Finding the First Maximal Independent Set. 81-85 BibTeX
Marta Cialdea: Some Remarks on the Possibility of Extending Resolution Proof Procedures to Intuitionistic Logic. 87-90 BibTeX
Pavel Goralcik, Václav Koubek: Verifying Nonrigidity. 91-95 BibTeX
Marc Snir: Exact Balancing is Not Always Good. 97-102 BibTeX
Max B. Webster, Paul W. Baker: A Class of Differential Equations for Testing Variable Step-Size Integration. 103-107 BibTeX

P. Srinivas Kumar, M. Manohar: On Probability of Forest of Quadtrees Reducing to Quadtrees. 109-111 BibTeX
Klaus Ambos-Spies: Inhomogeneities in the Polynomial-Time Degrees: The Degrees of Super Sparse Sets. 113-117 BibTeX
Franz Aurenhammer: The One-Dimensional Weighted Voronoi Diagram. 119-123 BibTeX
Arturo Carpi, Aldo de Luca: Square-Free Words on Partially Commutative Free Monoids. 125-131 BibTeX
Y. Hattori: Nonisomorphic Graphs with the Same T-Polynomial. 133-134 BibTeX
Françoise Gire: Two Decidability Problems for Infinite Words. 135-140 BibTeX
John Hughes: A Novel Representation of Lists and its Application to the Function "reverse". 141-144 BibTeX
Sylviane R. Schwer: On the Rationality of Petri Net Languages. 145-146 BibTeX
Lin Chen: O(1) Space Complexity Deletion for AVL Trees. 147-149 BibTeX
Ernest J. Cockayne, Denton E. Hewgill: Exact Computation of Steiner Minimal Trees in the Plane. 151-156 BibTeX
R. C. Shock: Computing the Minimum Cover of Functional Dependencies. 157-159 BibTeX
Michael Kallay: Convex Hull Made Easy. 161 BibTeX

Brigitte Jaumard, Michel Minoux: An Efficient Algorithm for the Transitive Closure and a Linear Worst-Case Complexity Result for a Class of Sparse Graphs. 163-169 BibTeX
J. Mark Keil: Total Domination in Interval Graphs. 171-174 BibTeX
Wolfgang Panny: A Note on the Higher Moments of the Expected Behavior of Straight Insertion Sort. 175-177 BibTeX
M. C. Hambury: Two Tagless Variations on the Deutsch-Schorr-Waite Algorithm. 179-183 BibTeX
Michael C. Loui, Teresa A. Matsushita, Douglas B. West: Election in a Complete Network with a Sense of Direction. 185-187 BibTeX
Svante Carlsson: Splitmerge - A Fast Stable Merging Algorithm. 189-192 BibTeX
Bruno Codenotti, Grazia Lotti: A Note on the VLSI Counter. 193-195 BibTeX
H. Gajewska, Robert Endre Tarjan: Deques with Heap Order. 197-200 BibTeX
Dana S. Richards: Data Compression and Gray-Code Sorting. 201-205 BibTeX
Key-Sun Choi, Gil-Chang Kim: A Controlled Quantification in Parsing of Montague Grammar. 207-216 BibTeX

Peter T. Highnam: Optimal Algorithms for Finding the Symmetries of a Planar Point Set. 219-222 BibTeX
Shaunak Pawagi, I. V. Ramakrishnan: An O(log n) Algorithm for Parallel Update of Minimum Spanning Trees. 223-229 BibTeX
Ming Li, Yaacov Yesha: String-Matching Cannot be Done by a Two-Head One-Way Deterministic Finite Automation. 231-235 BibTeX
J. B. Evans: Experiments with Trees of the Storage and Retrieval of Future Events. 237-242 BibTeX
Gopal K. Gupta, B. Srinivasan: Approximate Storage Utilization of B-Trees. 243-246 BibTeX
Paul Bourret, R. Souza de Oliveira: Lower and Upper Bounds of the Sizes of Domains: Estimates and Experiments. 247-253 BibTeX
Herbert J. Bernstein: Determining the Shape of a Convex n-Sided Polygon by Using 2n+k Tactile Probes. 255-260 BibTeX
Arthur M. Keller: Set-Theoretic Problems of Null Completion in Relational Databases. 261-265 BibTeX
Yannis Manolopoulos: Batched Search of Index Sequential Files. 267-272 BibTeX
Timo O. Alanko, R. L. Smelianski: On the Calculation of Control Transition Probabilities in a Program. 273-276 BibTeX

Thomas Lickteig: Gaussian Elimination is Optimal for Solving Linear Equations in Dimension Two. 277-279 BibTeX
Yoshito Hanatani, Ronald Fagin: A Simple Characterization of Database Dependency Implication. 281-283 BibTeX
Ian Parberry: On Recurrent and Recursive Interconnection Patterns. 285-289 BibTeX
Dan Gusfield, Leonard Pitt: Equivalent Approximation Algorithms for Node Cover. 291-294 BibTeX
Kunio Aizawa, Akira Nakamura: Direction-Independent Application of Productions on Two-Dimensional Arrays. 295-301 BibTeX
Frank K. H. A. Dehne: O(n^(1/2)) Algorithms for the Maximal Elements and ECDF Searching Problem on a Mesh-Connected Parallel Computer. 303-306 BibTeX
Krzysztof R. Apt, Dexter Kozen: Limits for Automatic Verification of Finite-State Concurrent Systems. 307-309 BibTeX
R. K. Arora, S. P. Rana, M. N. Gupta: Distributed Termination Detection Algorithm for Distributed Computations. 311-314 BibTeX
S. Sattolo: An Algorithm to Generate a Random Cyclic Permutation. 315-317 BibTeX
Ernst L. Leiss, C. Jitmedha: Horizontally and Vertically Bounded Propagation of Privileges. 319-327 BibTeX
Tadao Takaoka: An On-Line Pattern Matching Algorithm. 329-330 BibTeX