Information Processing Letters, Volume 30

Volume 30, Number 1, January 1989

M. J. Foster, Ronald I. Greenberg: Lower Bounds on the Area of Finite-State Machines. 1-7
Jeffrey S. Salowe: L-Infinity Interdistance Selection by Parametric Search. 9-14
Peter Roth: A Note on Word Chains and Regular Languages. 15-18
Philippe Darondeau: Bisimulation and Effectiveness. 19-20
Ravi S. Sandhu: The Reflected Tree Hierarchy for Protection and Sharing. 21-26
Andrzej Lingas, Marek Karpinski: Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. 27-32
P. P. Chakrabarti, Sujoy Ghose, A. Pandey, S. C. De Sarkar: Increasing Search Efficiency Using Multiple Heuristics. 33-36
György Turán: Lower Bounds for Synchronous Circuits and Planar Circuits. 37-40
Zvi Galil, Victor Y. Pan: Parallel Evaluation of the Determinant and of the Inverse of a Matrix. 41-45
Mihály Geréb-Graus, Ramamohan Paturi, Endre Szemerédi: There are no p-Complete Families of Symmetric Boolean Functions. 47-49
Eric C. R. Hehner: Real-Time Programming. 51-56

Rudolf Fleischer: Communication Complexity of Multi-Processor Systems. 57-65
Wing Shing Wong, Robert J. T. Morris: A New Approach to Choosing Initial Points in Local Search. 67-72
June H. Kim, Kyu Ho Park, Myunghwan Kim: A Model of Distributed Control: Dependency and Uncertainty. 73-77
Charles Consel, Olivier Danvy: Partial Evaluation of Pattern Matching in Strings. 79-86
Ron Shonkwiler: An Image Algorithm for Computing the Hausdorff Distance Efficiently in Linear Time. 87-89
Milena Mihail: On Coupling and the Approximation of the Permanent. 91-95
Charles U. Martel, Dan Gusfield: A Fast Parallel Quicksort Algorithm. 97-102
Peter van Emde Boas: Space Measures for Storage Modification Machines. 103-110

Toshiya Itoh, Shigeo Tsujii: An Efficient Algorithm for Deciding Quadratic Residuosity in Finite Fields GF(p_m). 111-114
Matti O. Jokinen: Customizable Garbage Collectors. 115-118
J. Scott Provan: Shortest Enclosing Walks and Cycles in Embedded Graphs. 119-125
Ornan Ori Gerstel, Yishay Mansour, Shmuel Zaks: Bit Complexity of Order Statistics on a Distributed Star Network. 127-132
José D. P. Rolim, Sheila A. Greibach: A Note on the Best-Case Complexity. 133-138
Udo Kelter: The Pitfall Paradox and its Solution with Virtual Objects. 139-143
Jørgen Staunstrup, Jürg Nievergelt: The Behavior of Shared Objects: Concepts, Pitfalls, and a New Model. 145-151
Karel Culik II: Variations of the Firing Squad Problem and Applications. 153-157
E. M. Ehlers, Sebastiaan H. von Solms: Using Random Context Structure Grammars to Represent Chemical Structures. 159-166

Christian Lavault: Average Number of Messages for Distributed Leader-Finding in Rings of Processors. 167-176
Houssine Chetto, Maryline Silly-Chetto: Scheduling Periodic and Sporadic Tasks in a Real-Time System. 177-184
James Wogulis: Self-Adjusting and Split Sequence Hash Tables. 185-188
Kerry Raymond: A Distributed Algorithm for Multiple Entries to a Critical Section. 189-193
Friedemann Mattern: Global Quiescence Detection Based on Credit Distribution and Recovery. 195-200
Ronald E. Barkley, T. Paul Lee: Point Representation and Hashing of an Interval. 201-203
Alok Aggarwal, Don Coppersmith, Daniel J. Kleitman: A Generalized Model for Understanding Evasiveness. 205-208
J. M. Robson: Separating Strings with Small Automata. 209-214
Joseph C. Culberson, Piotr Rudnicki: A Fast Algorithm for Constructing Trees from Distance Matrices. 215-220

K. Vidyasankar: An Elegant 1-Writer Multireader Multivalued Atomic Register. 221-223
Wojciech Rytter, Tomasz Szymacha: Parallel Algorithms for a Class of Graphs Generated Recursively. 225-231
Ludek Kucera: Graphs with Small Chromatic Numbers are Easy to Color. 233-236
Hock T. Ch'ng, B. Sprinivasan, Beng Chin Ooi: Study of Self-Organizing Heuristics for Skewed Access Patterns. 237-244
G. Song, D. Park, D. Lee, K. H. Park, M. Kim: A Distributed Deadlock Detection Algorithm: Distributed Graph Reconstruction Algorithm. 245-252
Yechezkel Zalcstein, Max H. Garzon: An NC₂ Algorithm for Testing Similarity of Matrices. 253-254
Dan Gusfield, Robert W. Irving: Parametric Stable Marriage and Minimum Cuts. 255-259
Moshe Y. Vardi: A Note on the Reduction of Two-Way Automata to One-Way Automata. 261-264
V. Raja, R. K. Ghosh, P. Gupta: An Efficient Parallel Algorithm for Random Sampling. 265-268
Edward Omiecinski, Eileen Tien Lin: A Hash-Based Join Algorithm for a Cube-Connected Parallel Computer. 269-275

J. L. Nazareth, K. A. Ariyawansa: On Accelerating Newton's Method Based on a Conic Model. 277-281
Aldo de Luca, Stefano Varricchio: Factorial Languages Whose Growth Function is Quadratically Upper Bounded. 283-288
G. Lindhorst, Farhad Shahrokhi: On Renaming a Set of Clauses as a Horn Set. 289-293
Oscar H. Ibarra, Tao Jiang: Optimal Simulation of Tree Arrays by Linear Arrays. 295-302
Carsten Vogt: A New Approach to Optimal Cache Scheduling. 303-310