Information Processing Letters, Volume 23

Volume 23, Number 1, July 1986

Wojciech Rytter: The Space Complexity of the Unique Decipherability Problem. 1-3
Ferng-Ching Lin, Wei Kuan Shih: Long Edges in the Layouts of Shuffle-Exchange and Cube-Connected Cycles Graphs. 5-9
Gottfried Tinhofer, H. Schreck: The Bounded Subset Sum Problem is Almost Everywhere Randomly Decidable in O(n). 11-17
Hartmut Schmeck: On the Maximum Edge Length in VLSI Layouts of Complete Binary Trees. 19-23
José L. Balcázar: On (Greek D)D_P²-Immunity. 25-28 Karel Culik II, Juhani Karhumäki: A Note on the Equivalence Problem of Rational Formal Power Series. 29-31
K. Kakuta, Hirofumi Nakamura, S. Iida: A Parallel Reference Counting Algorithm. 33-37
Bernd-Jürgen Falkowski, Lothar Schmitz: A Note on the Queens' Problem. 39-46
O. M. Vikas, S. K. Basandra: Data Algebra and Its Application in Database Design. 47-54

Ivan Lavallée, Gérard Roucairol: A Fully Distributed (Minimal) Spanning Tree Algorithm. 55-62
Alberto Apostolico: Improving the Worst-Case Performance of the Hunt-Szymanski Strategy for the Longest Common Subsequence of Two Strings. 63-69
Hans Rohnert: Shortest Paths in the Plane with Convex Polygonal Obstacles. 71-76
Rob R. Hoogerwoord: An Implementation of Mutual Inclusion. 77-80
Wojciech Rytter: An Application of Mehlhorn's Algorithm for Bracket Languages to log(n) Space Recognition of Input-Driven Languages. 81-84
Janusz W. Laski: An Algorithm for the Derivation of Codefinitions in Computer Programs. 85-90
J. K. Annot, M. D. Janssens, A. J. van de Goor: Comments on Morris's Starvation-Free Solution to the Mutual Exclusion Problem. 91-97
Simeon C. Ntafos: On Gallery Watchmen in Grids. 99-102
John V. Franco: On the Probabilistic Performance of Algorithms for the Satisfiability Problem. 103-106
Bruno Codenotti, Grazia Lotti: Area-Time Tradeoffs for Bilinear Forms Computations in VLSI. 107-109

Bruno Codenotti, Grazia Lotti: A VLSI Fast Solver for Tridiagonal Linear Systems. 111-114
O. M. Makarov: A Noncommutative Algorithm for Multiplying 5*5 Matrices Using 102 Multiplications. 115-117
Ten-Hwang Lai, Alan P. Sprague: A Note on Anomalies in Parallel Branch-and-Bound Algorithms with One-to-One Bounding Functions. 119-122
J. Cooper, Selim G. Akl: Efficient Selection on a Binary Tree. 123-126
Patricio V. Poblete: Approximating Functions by Their Poisson Transform. 127-130
Alan A. Bertossi: Total Domination in Interval Graphs. 131-134
Wojciech Szpankowski: On an Asymptotic Analysis of a Tree-Type Algorithm for Broadcast Communications. 135-142
Klaus W. Wagner: On the Intersection of the Class of Linear Context-Free Languages and the Class of Single-Reset Languages. 143-146
Grigori Mints, Enn Tyugu: Semantics of a Declarative Language. 147-151
Kazem Taghva: Some Characterizations of Finitely Specifiable Implicational Dependency Families. 153-158
Jan Tijmen Udding: Absence of Individual Starvation Using Weak Semaphores. 159-162

Patrick Dehornoy: Turing Complexity of the Ordinals. 167-170
Michel Latteux, Erick Timmerman: Finitely Generated (Omega)o-Languages. 171-175
Bowen Alpern, Alan J. Demers, Fred B. Schneider: Safety Without Stuttering. 177-180
David R. O'Hallaron, P. E. Reynolds: A Generalized Deadlock Predicate. 181-188
Lenore Blum: Towards an Asymptotic Analysis of Karmarkar's Algorithm. 189-194
Alan A. Bertossi, Maurizio A. Bonuccelli: Hamiltonian Circuits in Interval Graph Generalizations. 195-200
Susumu Yamasaki, Shuji Doshita: Resolution Deduction to Detect Satisfiability For Another Class Including Non-Horn Sentences In Propositional Logic. 201-207
D. Gordon: Eliminating the Flag in Threaded Binary Search Trees. 209-214
O. J. Murphy, Stanley M. Selkow: The Efficiency of Using k-d Trees for Finding Nearest Neighbors in Discrete Space. 215-218

R. Sommerhalder, S. C. van Westrhenen: A Parallel O(log n) Algorithm for the Drawing of Algebraic Curves in an n*n Square. 221-226
Klaus Ambos-Spies: A Note on the Complete Problems for Complexity Classes. 227-230
Jan L. A. van de Snepscheut, Jan Tijmen Udding: An Alternative Implementation of Communication Primitives. 231-238
David J. Evans, Nadia Y. Yousif: Merging by the Parallel Jump Searching Algorithm. 239-246
G. Chen, M. Howard Williams: The Value of an Array Facility in Prolog. 247-251
Manfred Broy: Denotational Semantics of Communicating Sequential Programs. 253-259
J. Stojanovski: A Note on Implementing Prolog in Lisp. 261-264
C. C. Handley: An in Situ Distributive Sort. 265-270
Erkki Mäkinen: A Note on Pure Grammars. 271-274

Ernst L. Leiss: The Inaccessible Set: A Classification by Query Type of Security Risks in Statistical Database. 275-279
M. Benois, Jacques Sakarovitch: On the Complexity of Some Extended Word Problems Defined by Cancellation Rules. 281-287
Herbert Edelsbrunner, Emo Welzl: Halfplanar Range Search in Linear Space and O(n^(0.695)) Query Time. 289-293
Alain J. Martin: A New Generalization of Dekker's Algorithm for Mutual Exclusion. 295-297
Leszek Holenderski: The Correctness of Nondeterministic Programs Revisited. 299-303
Lloyd Allison, Trevor I. Dix: A Bit-String Longest-Common-Subsequence Algorithm. 305-310
Kwang-Moo Choe, C. H. Chang: Efficient Computation of the Locally Least-Cost Insertion String for the LR Error Repair. 311-316
Frank Harary, Peter J. Slater: A Linear Algorithm for the Cutting Center of a Tree. 317-319
Richard B. Kieburtz: When Chasing Your Tail Saves Time. 321-324
Ikuo Nakata, Masataka Sassa: L-Attributed LL(1)-Grammars are LR-Attributed. 325-328