Information Processing Letters, Volume 55

Volume 55, Number 1, 7 July 1995

Chung-Ming Huang, Jenq-Muh Hsu, Shiun-Wei Lee:
ECFSM-Based Probabilistic Protocol Verification. 1-9
Ton Kloks, Dieter Kratsch:
Computing a Perfect Edge Without Vertex Elimination Ordering of a Chordal Bipartite Graph. 11-16
Dawei Hong, Joseph Y.-T. Leung:
Probabilistic Analysis of k-Dimensional Packing Algorithms. 17-24
Ferruccio Barsi, Maria Cristina Pinotti:
A Fully Parallel Algorithm for Residue to Binary Conversion. 25-26
, Addendum: Inf. Process. Lett. 56(2): 121(1995)
Meena Mahajan, N. V. Vinodchandran:
A Note on Mod and Generalised Mod Classes. 27-31
Walter Vogler:
Fairness and Partial Order Semantics. 33-39
Alak Kumar Datta, Ranjan K. Sen:
1-Approximation Algorithm for Bottleneck Disjoint Path Matching. 41-44
Hung-Yu Lin, Lein Harn:
Fair Reconstruction of a Secret. 45-47
Fouad B. Chedid:
On the Generalized Twisted Cube. 49-52
Paul Cull, Shawn M. Larson:
On Generalized Twisted Cubes. 53-55
Gregory Butler:
Easy Verification of Behavioural Subtyping in Common Cases. 57-58

Jeffery Westbrook, Dicky C. K. Yan:
Linear Bounds for On-Line Steiner Problems. 59-63
Steve Hill:
The Lazy Z-Buffer. 65-70
Ramjee P. Swaminathan, D. Giriraj, D. K. Bhatia:
The Pagenumber of the Class of Bandwidth-k Graphs is k-1. 71-74
Muhammad H. Alsuwaiyel, D. T. Lee:
Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon. 75-79
Jie Wang:
Some Results on Selectivity and Self-Reducibility. 81-87
John D. Valois:
A 3-Valued Wakeup Protocol. 89-93
Youssef Saab:
Iterative Improvement of Vertex Covers. 95-98
Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague:
Simple Linear Time Recognition of Unit Interval Graphs. 99-104
A. Dermouche:
A Fast Algorithm for String Matching with Mismatches. 105-110
Tien Huynh, Kim Marriott:
Incremental Constraint Deletion in Systems of Linear Constraints. 111-115

Mukesh Singhal, Friedemann Mattern:
An Optimality Proof for Asynchronous Recovery Algorithms in Distributed Systems. 117-121
Pranava K. Jha, Giora Slutzki:
A Scheme to Construct Distance Three Codes Using Latin Squares, with Applications to the n-Cube. 123-127
Béatrice Bérard:
Untiming Timed Languages. 129-135
Hongchi Shi, Gerhard X. Ritter, Joseph N. Wilson:
Simulations Between Two Reconfigurable Mesh Models. 137-142
Borislav Nikolik:
Constraint Preservation Through Loops. 143-148
Ortrud Oellermann, Jeremy Spinrad:
A Polynomial Algorithm for Testing Whether a Graph is 3-Steiner Distance Hereditary. 149-154
Ee-Chien Chang, Chee-Keng Yap:
A Note on Improved Deterministic Time Simulation of Nondeterministic Space for Small Space. 155-157
Lydia E. Kavraki, Mihail N. Kolountzakis:
Partitioning a Planar Assembly Into Two Connected Parts is NP-Complete. 159-165
Li Gong:
Collisionful Keyed Hash Functions with Selectable Collisions. 167-170
Walter Hower:
Constraint Satisfaction - Algorithms and Complexity Analysis. 171-178

Rainer Schuler:
Some Properties of Sets Tractable Under Every Polynomial-Time Computable Distribution. 179-184
Nguyen Huong Lam:
A Note on Codes Having no Finite Completions. 185-188
Carlo Blundo:
A Note on Dynamic Threshold Schemes. 189-193
Jörg Keller, Thomas Walle:
A Note on Implementing Combining Networks. 195-200
Simon Atkinson, David Scholefield:
Transformational vs Reactive Refinement in Real-Time Systems. 201-210
K. Thirusangu, K. Rangarajan:
A Note on the Construction of Marked Graphs. 211-215
Xavier Droubay:
Palindromes in the Fibonacci Word. 217-221
Xuehou Tan, Xiaoyu Song:
Hexagonal Three-Layer Channel Routing. 223-228
Young Park, Benjamin Goldberg:
Static Analysis for Optimizing Reference Counting. 229-234

Tatsuya Akutsu:
Approximate String Matching with don't Care Characters. 235-239
J. Ramachandran:
Modulo Classes and Logarithmic Advice. 241-245
Gwoboa Horng:
Password Authentication Without Using a Password Table. 247-250
Kian-Lee Tan, Hongjun Lu:
Workload Scheduling for Multiple Query Processing. 251-257
Lin Chen:
Solving the Shortest-Paths Problem on Bipartite Permutation Graphs Efficiently. 259-264
Soojung Lee, Junguk L. Kim:
Resolving all Deadlocks in Distributed Systems. 265-271
Tung-Shou Chen:
SIMPLE: An Optimal Disk System with Two Restricted Heads. 273-277
Hing Leung, Desh Ranjan, Héctor J. Hernández, D. T. Tang, Agustin González:
A Simple Proof on the Decidability of Equivalence Between Recursive and Nonrecursive Datalog Programs. 279-282
Ung Kyu Park, Hwang Kyu Choi, Tag Gon Kim:
Uniform Partitioning of Relations Using Histogram Equalization Framework: An Efficient Parallel Hash-Based Join. 283-289
Serdar Boztas:
A Robust Multi-Priority Topology-Independent Transmission Schedule for Packet Radio Networks. 291-295

Martin Farach, Teresa M. Przytycka, Mikkel Thorup:
On the Agreement of Many Trees. 297-301
Zhi-Zhong Chen:
A Fast and Efficient NC Algorithm for Maximal Matching. 303-307
Jürg Nievergelt, Narsingh Deo:
Metric Graphs Elastically Embeddable in the Plane. 309-315
Pallab Dasgupta, P. P. Chakrabarti, S. C. De Sarkar:
Utility of Pathmax in Partial Order Heuristic Search. 317-322
Vasco Thudichum Vasconcelos:
Unification of Kinded Infinite Trees. 323-328
Andrei Z. Broder, Alan M. Frieze, Carsten Lund, Steven Phillips, Nick Reingold:
Balanced Allocations for Tree-Like Inputs. 329-332
Weifa Liang:
Fast Parallel Algorithms for the Approximate Edge-Coloring Problem. 333-338
Amiya Nayak, Vincenzo Acciaro, Paolo Gissi:
A Note on Isomorphic Chordal Rings. 339-341
Young Gil Park, Benjamin Goldberg:
Order-of-Demand Analysis for Lazy Languages. 343-348
Gisela Pitsch:
LR(k)-Coupled-Context-Free Grammars. 349-358