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

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

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

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

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

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