Information Processing Letters, Volume 27

Volume 27, Number 1, February 1988

M. Balakrishnan, S. Sutarwala, Arun K. Majumdar, Dilip K. Banerji, James G. Linders: A Semantic Approach for Modular Synthesis of VLSI Systems. 1-7 BibTeX
Ming Li: A Separator Theorem for One-Dimensional Graphs Under Linear Mapping. 9-11 BibTeX
Mikhail J. Atallah, Greg N. Frederickson, S. Rao Kosaraju: Sorting with Efficient Use of Special-Purpose Sorters. 13-15 BibTeX
G. Ramalingam, C. Pandu Rangan: Total Domination in Interval Graphs Revisited. 17-21 BibTeX
G. Lyon: A Tagless Marking That is Linear Over Subtrees. 23-28 BibTeX
Mark B. Josephs: The Data Refinement Calculator for Z Specifications. 29-33 BibTeX
Doug Lea: Digital and Hilbert k-d Trees. 35-41 BibTeX
Alan Gibbons, Amos Israeli, Wojciech Rytter: Parallel O(log n) Time Edge-Colouring of Trees and Halin Graphs. 43-51 BibTeX

Bogdan S. Chlebus: A Parallel Bucket Sort. 57-61 BibTeX
Jacek Witaszek: A Practical Method for Finding the Optimum Postponement Transformation for LR(k) Parsers. 63-67 BibTeX
Mukesh Singhal, Yelena Yesha: A Polynomial Algorithm for Computation of the Probability of Conflicts in a Database Under Arbitrary Data Access Distribution. 69-74 BibTeX
Satoru Miyano: A Parallelizable Lexicographically First Maximal Edge-Induced Subgraph Problem. 75-78 BibTeX
Chin-Chen Chang, C. H. Chang: An Ordered Minimal Perfect Hashing Scheme with Single Parameter. 79-83 BibTeX
Robin Liu, Simeon C. Ntafos: On Decomposing Polygons into Uniformly Monotone Parts. 85-89 BibTeX
Franz Baader: A Note on Unification Type Zero. 91-93 BibTeX
Ravi S. Sandhu: Cryptographic Implementation of a Tree Hierarchy for Access Control. 95-98 BibTeX
Nicholas J. Patterson, Kenneth J. Supowit: Finding the Vertices Nearest to a Point in a Hypercube. 99-102 BibTeX
Alan M. Frieze: On the Random Construction of Heaps. 103-109 BibTeX

Leszek Holenderski, Andrzej Szalas: Propositional Description of Finite Cause-Effect Structures. 111-117 BibTeX
David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: On Generating All Maximal Independent Sets. 119-123 BibTeX
Kurt Mehlhorn: A Faster Approximation Algorithm for the Steiner Problem in Graphs. 125-128 BibTeX
Sharat Chandran, Azriel Rosenfeld: Order Statistics on a Hypercube. 129-132 BibTeX
Alan A. Bertossi: Parallel Circle-Cover Algorithms. 133-139 BibTeX
Stephen A. Cook, Michael Luby: A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula. 141-145 BibTeX
Joel Berman, Willem J. Blok: Positive Boolean Dependencies. 147-150 BibTeX
Osamu Watanabe: On Hardness of One-Way Functions. 151-157 BibTeX
Jacek Leszczylowski, Staffan Bonnier, Jan Maluszynski: Logic Programming with External Procedures: Introducing S-Unification. 159-165 BibTeX

Yung H. Tsin: On Handling Vertex Deletion in Updating Spanning Trees. 167-168 BibTeX
K. V. S. Ramarao, Robert Daley, Rami G. Melhem: Message Complexity of the Set Intersection Problem. 169-174 BibTeX
Hans Rohnert: Time and Space Efficient Algorithms for Shortest Paths Between Convex Polygons. 175-179 BibTeX
Richard Koo, Sam Toueg: Effects of Message Loss on the Termination of Distributed Protocols. 181-188 BibTeX
Ulrich Faigle, Rainer Schrader: On the Convergence of Stationary Distributions in Simulated Annealing Algorithms. 189-194 BibTeX
Abdol-Hossein Esfahanian, S. Louis Hakimi: On Computing a Conditional Edge-Connectivity of a Graph. 195-199 BibTeX
Andrzej Szepietowski: Remarks on Languages Acceptable in log n Space. 201-203 BibTeX
Dominique Roelants van Baronaigien, Frank Ruskey: Generating t-ary Trees in A-Order. 205-213 BibTeX
Khaled M. Bugrara, Paul Walton Purdom Jr.: An Exponential Lower Bound for the Pure Literal Rule. 215-219 BibTeX

Carla D. Savage:
Recognizing Majority on a One-Way Mesh. 221-225
Electronic Edition (link) BibTeX
Hermann Jung, Kurt Mehlhorn:
Parallel Algorithms for Computing Maximal Independent Sets in Trees and for Updating Minimum Spanning Trees. 227-236
Electronic Edition (link) BibTeX
Krishnaprasad Thirunarayan:
On the Computability of Circumscription. 237-243
Electronic Edition (link) BibTeX
Bob P. Weems:
A Study of Page Arrangements for Extendible Hashing. 245-248
Electronic Edition (link) BibTeX
Ashok Kumar, Vishv M. Malhotra:
A New Computation Rule for Prolog. 249-252
Electronic Edition (link) BibTeX
Kozo Itano, Yutaka Sato, Hidemi Hirai, Tomoyoshi Yamagata:
An Incremental Pattern Matching Algorithm for the Pipelined Lexical Scanner. 253-258
Electronic Edition (link) BibTeX
Harold N. Gabow, Robert Endre Tarjan:
A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest. 259-263
Electronic Edition (link) BibTeX
Mirko Krvanek:
The Complexity of Ultrametric Partitions on Graphs. 265-270
Electronic Edition (link) BibTeX
G. Ramalingam, C. Pandu Rangan:
A Unified Approach to Domination Problems on Interval Graphs. 271-274
Electronic Edition (link) BibTeX

Jirí Matousek: Line Arrangements and Range Search. 275-280 BibTeX
Aldo de Luca, Stefano Varricchio: On the Factors of the Thue-Morse Word on Three Symbols. 281-285 BibTeX
Hans L. Bodlaender: A Better Lower Bound For Distributed Leader Finding in Bidirectional, Asynchronous Rings of Processors. 287-290 BibTeX
Meichun Hsu, Stuart E. Madnick: Shifting Timestamps for Concurrency Control in an Information Hierarchy. 291-297 BibTeX
Shay Kutten: Optimal Fault-Tolerant Distributed Construction of a Spanning Forest. 299-307 BibTeX
Ewa Orlowska: Proof System for Weakest Prespecification. 309-313 BibTeX
M. A. Sridhar: On the Connectivity of the De Bruijn Graph. 315-318 BibTeX
Xiaoqiu Huang: A Lower Bound for the Edit-Distance Problem Under an Arbitrary Cost Function. 319-321 BibTeX
David Fernández-Baca: Nonserial Dynamic Programming Formulations of Satisfiability. 323-326 BibTeX