Information Processing Letters, Volume 22

Volume 22, Number 1, January 1986

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

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

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

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

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

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