Information Processing Letters, Volume 14

Volume 14, Number 1, 27 March 1982

Alfred Schmitt: On the Computational Power of the Floor Function. 1-3
Ben-Zion Chor: Arithmetic of Finite Fields. 4-6
Dhruva Nath, S. N. Maheshwari: Parallel Algorithms for the Connected Components and Minimal Spanning Tree Problems. 7-11
Andries E. Brouwer, Peter van Emde Boas: A Note on `Master Keys for Group Sharing'. 12-14
Roland Carl Backhouse: Writing a Number as a Sum of Two Squares: A New Solution. 15-17
Erol Gelenbe, Danièle Gardy: On the Size of Projections: I. 18-21
Hamish I. E. Gunn: Compile Time Type Checking of Structure Field Accessing. 22-25
Robert Endre Tarjan: A Hierarchical Clustering Algorithm Using Strong Components. 26-29
Robert Endre Tarjan: Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. 30-33
Jan van Leeuwen, Maurice Nivat: Efficient Recognition of Rational Relations. 34-38
Ker-I Ko: Some Observations on the Probabilistic Algorithms and NP-hard Problems. 39-43
Shmuel Zaks: Generation and Ranking of k-ary Trees. 44-48

Luis Fariñas del Cerro: A Simple Deduction Method for Modal Logic. 49-51
A. O. Slisenko: Context-Free Grammars as a Tool for Describing Polynomial-Time Subclasses of Hard Problems. 52-56
Marc H. Graham, Alberto O. Mendelzon: Strong Equivalence of Relational Wxpressions Under Dependencies. 57-62
J. C. Lagarias, Donald E. Swartwout: Minimal Storage Representations for Binary Relations. 63-66
Giuseppina C. Gini: The Automatic Synthesis of Iterative Programs. 67-73
Herbert Edelsbrunner, Hermann A. Maurer, David G. Kirkpatrick: Polygonal Intersection Searching. 74-79
Jan A. Bergstra, John-Jules Ch. Meyer: A Simple Transfer Lemma for Algebraic Specifications. 80-85
Eli Upfal: Formal Correctness Proofs of a Nondeterministic Program. 86-92
Ludek Kucera: Parallel Computation and Conflicts in Memory Access. 93-96 , Erratum and Addendum: IPL 17(2): 107 (1983)

Takashi Yokomori, Derick Wood, Klaus-Jörn Lange: A Three-Restricted Normal Form Theorem for ET0L Languages. 97-100 , Erratum: Information Processing Letters 21(1): 53 (1985)
Jorma Tarhio: LR Parsing of Some Ambiguous Grammars. 101-103
Dietmar Wätjen, Werner Struckmann: An Algorithm for Verifying Equations of Morphisms in a Category. 104-108
K. N. King, Barbara Smith-Thomas: An Optimal Algorithm for Sink-Finding. 109-111
Jean-Louis Lassez, V. L. Nguyen, Liz Sonenberg: Fixed Point Theorems and Semantics: A Folk Tale. 112-116
R. H. Barlow, D. J. Evans, J. Shanehchi: Parallel Multisection for the Determination of the Eigenvalues of Symmetric Quindiagonal Matrices. 117-118
Johannes Röhrich: A Hybrid of Quicksort with O(n log n) Worst Case Complexity. 119-123
Herbert Edelsbrunner, Mark H. Overmars: On the Equivalence of Some Rectangle Problems. 124-127
Calvin C. Elgot, Alan J. Perlis, Lawrence Snyder: A Syntax-Free Semantics for the APL Operators. 128-131
Dzenan Ridjanovic, Michael L. Brodie: Defining Database Dynamics with Attribute Grammars. 132-138
James F. Korsh: Growing Nearly Optimal Binary Search Trees. 139-143
Dario Bini: Reply to the Paper "The Numerical Instability of Bini's Algorithm". 144-145

Matti Jakobsson: Evaluation of a Hierarchical Bit-Vector Compression Technique. 147-149
Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. 150-157
Hiroshi Umeo, Kenichi Morita, Kazuhiro Sugata: Deterministic One-Way Simulation of Two-Way Real-Time Cellular Automata and Its Related Problems. 158-161
Giordano Beretta: Monte Carlo Estimation of Numerical Stability in Fast Algorithms for Systems of Bilinear Forms. 162-167
Paul Franchi-Zannettacci: An Extension to Trees of the Sardinas and Patterson Algorithm. 168-173
Robert Demolombe: Generalized Division for Relational Algebraic Language. 174-178
Ernst-Erich Doberkat: Asymptotic Estimates for the Higher Moments of the Expected Behavior of Straight Insertion Sort. 179-182
Michael J. Fischer, Nancy A. Lynch: A Lower Bound for the Time to Assure Interactive Consistency. 183-186
Jiann H. Jou, Patrick C. Fischer: The Complexity of Recognizing 3NF Relation Schemes. 187-190
Jack Minker, Guy Zanon: An Extension to Linear Resolution with Selection Function. 191-194

Clelia de Felice: On the Triangle Conjecture. 197-200
F. Warren Burton: A Linear Space Translation of Functional Programs to Turner Combinators. 201-204
F. Warren Burton: An Efficient Functional Implementation of FIFO Queues. 205-206
Anton Nijholt: A Note on the Sufficiency of Sokolowski's Criterion for Context-Free Languages. 207
P. G. Reddy, Subhash Bhalla, Bandreddi E. Prasad: A Model of Concurrency Control in Distributed Database Systems. 208-213
J. George Shanthikumar: A Recursive Algorithm to Generate Joint Probability Distribution of Arrivals from Exponential Sources During a Random Time Interval. 214-217
Johnson M. Hart: Permutation Inversions and Multidimensional Cumulative Distribution Functions. 218-222
David A. Carlson, John E. Savage: Extreme Time-Space Tradeoffs for Graphs with Small Space Requirements. 223-227
Reuven Bar-Yehuda, Uzi Vishkin: Complexity of Finding k-Path-Free Dominating Sets in Graphs. 228-232
Carla D. Savage: Depth-First Search and the Vertex Cover Problem. 233-237
Heinz Zemanek: Obituary: Victor Mikhaylovich Glushkov (1923-1982). 236-237