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

Last update Thu May 23 15:01:59 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page