Information Processing Letters, Volume 26

Volume 26, Number 1, September 1987

Brigitte Jaumard, Bruno Simeone: On the Complexity of the Maximum Satisfiability Problem for Horn Formulas. 1-4
James R. Driscoll, Sheau-Dong Lang, LeRoy A. Franklin: Modeling B-Tree Insertion Activity. 5-18
Alfs T. Berztiss: A Notation for Distributed Operations. 19-21
Jean Berstel, Srecko Brlek: On the Length of Word Chains. 23-28
Ronald V. Book, Hai-Ning Liu: Rewriting Systems and Word Problems in a Free Partially Commutative Monoid. 29-32
Svante Carlsson: The Deap-A Double-Ended Heap to Implement Double-Ended Priority Queues. 33-36
Janet Incerpi, Robert Sedgewick: Practical Variations of Shellsort. 37-43
Jean-Claude Bermond, Jean-Michel Fourneau, Alain Jean-Marie: Equivalence of Multistage Interconnection Networks. 45-50
László Babai: Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. 51-53

Yves Métivier, Edward Ochmanski: On Lexicographic Semi-Commutations. 55-59
Xiaojun Shen, Herbert Edelsbrunner: A Tight Lower Bound on the Size of Visibility Graphs. 61-64
Michaël Rusinowitch: On Termination of the Direct Sum of Term-Rewriting Systems. 65-70
Andranik Mirzaian: A Halving Technique for the Longest Stuttering Subsequence Problem. 71-75
Jan Magott: Performance Evaluation of Concurrent Systems Using Conflict-Free and Persistent Petri Nets. 77-80
Zvi Galil, Moti Yung: Partitioned Encryption and Achieving Simultaneity by Partitioning. 81-88
C. Mathieu, Claude Puech, Hossein Yahia: Average Efficiency of Data Structures for Binary Image Processing. 89-93
K. G. Subramanian, Rani Siromoney, P. J. Abisha: A D0L-T0L Public Key Cryptosystem. 95-97
Ajay K. Gupta, Susanne E. Hambrusch: Optimal Three-Dimensional Layouts of Complete Binary Trees. 99-104
Matthew Thazhuthaveetil, Andrew R. Pleszkun: On the Structural Locality of Reference in LISP List Access Streams. 105-110

Andrzej Szalas: Arithmetical Axiomatization of First-Order Temporal Logic. 111-116
Ondrej Sýkora, Imrich Vrto: Tight Chip Area Lower Bounds for String Matching. 117-119
M. Zhu, N. K. Loh, Pepe Siy: Towards the Minimum Set of Primitive Relations in Temporal Logic. 121-126
Y. Hou: Trinity Algebra and its Application to Machine Decompositions. 127-134
A. S. M. Sajeev, J. Olszewski: Manipulation of Data Structures Without Pointers. 135-143
Shlomo Moran, Yaron Wolfstahl: Extended Impossibility Results for Asynchronous Complete Networks. 145-151
Johan Håstad: One-Way Permutations in NC0. 153-155
Michael R. Fellows, Michael A. Langston: Nonconstructive Advances in Polynomial-Time Complexity. 155-162

Krzysztof R. Apt, Luc Bougé, Ph. Clermont: Two Normal Form Theorems for CSP Programs. 165-171
Michael T. Goodrich: Finding the Convex Hull of a Sorted Point Set in Parallel. 173-179
Ursula Martin: Extension Functions for Multiset Orderings. 181-186
Shlomit S. Pinter, Yaron Wolfstahl: Embedding Ternary Trees in VLSI Arrays. 187-191
Ulrich Güntzer, Manfred Paul: Jump Interpolation Search Trees and Symmetric Binary Numbers. 193-204
Tadao Takaoka: A Decomposition Rule for the Hoare Logic. 205-208
Alberto Apostolico, Susanne E. Hambrusch: Finding Maximum Cliques on Circular-Arc Graphs. 209-215
C. Baleanu, D. Tomescu: An Architecture for Symbolic Processing. 217-222

Claudio Arbib: A Polynomial Characterization of Some Graph Partitioning Problems. 223-230
Karel Culik II, Juhani Karhumäki: On Totalistic Systolic Networks. 231-236
Andrzej Sieminski: Fast Decoding of the Huffman Codes. 237-241
Carroll Morgan: Data Refinement by Miracles. 243-246
Patrick W. Dymond: Input-Driven Languages are in log n Depth. 247-250
Eljas Soisalon-Soininen, Jorma Tarhio: Looping LR Parsers. 251-253
Klaus Hinrichs, Jürg Nievergelt, Peter Schorn: Plane-Sweep Solves the Closest Pair Problem Elegantly. 255-261
Olivier Y. de Vel, E. V. Krishnamurthy: An Iterative Pipelined Array Architecture for the Generalized Matrix Inversion. 263-267
Stephen A. Cook: Short Propositional Formulas Represent Nondeterministic Computations. 269-270
Erkki Mäkinen: On the Rotation Distance of Binary Trees. 271-272
Joel I. Seiferas: A Variant of Ben-Or's Lower Bound for Algebraic Decision Trees. 273-276

Ganesh Gopalakrishnan, Mandayam K. Srivas: Implementing Functional Programs Using Mutable Abstract Data Types. 277-286
Tat-hung Chan: The Boundedness Problem for Three-Dimensional Vector Addition Systems with States. 287-289
Bruce M. Maggs, Serge A. Plotkin: Minimum-Cost Spanning Tree as a Path-Finding Problem. 291-293
Richard J. Cole: An Optimally Efficient Selection Algorithm. 295-299
Israel Cidon: Yet Another Distributed Depth-First-Search Algorithm. 301-305
Rolf G. Karlsson, Mark H. Overmars: Normalized Divide-and-Conquer: A Scaling Technique for Solving Multi-Dimensional Problems. 307-312
Ludwik Czaja: Cause-Effect Structures. 313-319
Marc Bezem, Jan van Leeuwen: On Estimating the Complexity of Logarithmic Decompositions. 321-324
John R. Gilbert: Some Nested Dissection Order is Nearly Optimal. 325-328