Information Processing Letters, Volume 39

Volume 39, Number 1, 12 July 1991

Robert Nieuwenhuis, Pilar Nivela: Efficient Deduction in Equality Horn Logic by Horn-Completion. 1-6
Ronald V. Book: On Random Oracle Separations. 7-10
Bernadette Charron-Bost: Concerning the Size of Logical Clocks in Distributed Systems. 11-16
Alberto Apostolico, Martin Farach, Costas S. Iliopoulos: Optimal Superprimitivity Testing for Strings. 17-20
Jianer Chen, Jim Cox, Bud Mishra: An NL Hierarchy. 21-26
Ronald A. Olsson, Daniel T. Huang: Axiomatic Semantics for ``Escape'' Statements. 27-33
Roberto Tamassia, Ioannis G. Tollis, Jeffrey Scott Vitter: Lower Bounds for Planar Orthogonal Drawings of Graphs. 35-40
Elena Stöhr: Broadcasting in the Butterfly Network. 41-43
A. Prasad Sistla: Proving Correctness with Respect to Nondeterministic Safety Specifications. 45-49
Fabrizio Luccio, Linda Pagli: An Efficient Algorithm for Some Tree Matching Problems. 51-57

Alexander A. Shvartsman: Achieving Optimal CRCW PRAM Fault-Tolerance. 59-66
Ilan Newman: Private vs. Common Random Bits in Communication Complexity. 67-71
Amos Omondi: Fast One's-Complement Multiplication. 73-79
Roberto Grossi: A Note on the Subtree Isomorphism for Ordered Trees and Related Problems. 81-84
Sandy Irani, Ronitt Rubinfeld: A Competitive 2-Server Algorithm. 85-91
Jang-Ping Sheu: Fault-Tolerant Parallel k Selection Algorithm in n-Cube Networks. 93-97
Abdulla Bataineh, Füsun Özgüner, Alok Sarwal: Parallel Boolean Operations for Information Retrieval. 99-108
Alessandro Fantechi, Stefania Gnesi: Compositionality and Bisimulation: A Negative Result. 109-114

Pierre Fraigniaud, Claudine Peyrat: Broadcasting in a Hypercube when Some Calls Fail. 115-119
M. Keil: A Simple Algorithm for Determining the Envelope of a Set of Lines. 121-124
Ke Qiu, Henk Meijer, Selim G. Akl: Decomposing a Star Graph Into Disjoint Cycles. 125-129
Bing-Chao Huang, Michael A. Langston: Stable Set and Multiset Operations in Optimal Time and Space. 131-136
Hans-Ulrich Simon: The Vapnik-Chervonenkis Dimension of Decision Trees with Bounded Rank. 137-141
Prabhakar Ragde, Avi Wigderson: Linear-Size Constant-Depth Polylog-Treshold Circuits. 143-146
Nian-Shing Chen, Hwey-Pyng Yu, Shing-Tsaan Huang: A Self-Stabilizing Algorithm for Constructing Spanning Trees. 147-151
Paul J. Heffernan: The Translation Square Map and Approximate Congruence. 153-159
Janice Jeffs: Order Independent NCE Grammars Recognized in Polynomial Time. 161-164
M. L. Garg, S. I. Ahson, P. V. Gupta: A Fuzzy Petri Net for Knowledge Representation and Reasoning. 165-171

Sandeep Sen: Some Observations on Skip-Lists. 173-176
Tatsuya Motoki: Inductive Inference from all Positive and Some Negative Data. 177-182
Jirí Matousek: Randomized Optimal Algorithm for Slope Selection. 183-187
Dominique Roelants van Baronaigien: A Loopless Algorithm for Generating Binary Tree Sequences. 189-194
Svante Carlsson, Jingsen Chen: An Optimal Parallel Adaptive Sorting Algorithm. 195-200
Volker Turau: Fixed-Radius Near Neighbors Search. 201-203
Christos Levcopoulos, Ola Petersson: Splitsort - An Adaptive Sorting Algorithm. 205-211
Robert J. T. Morris, Wing Shing Wong: Systematic Choice of Initial Points in Local Search: Extensions and Application to Neural Networks. 213-217
Thomas Hofmeister, Walter Hohberg, Susanne Köhling: Some Notes on Threshold Circuits, and Multiplication in Depth 4. 219-225
Jeremy Spinrad: Finding Large Holes. 227-229

Achim Schweikard: Trigonometric Polynomials with Simple Roots. 231-236
Abhay K. Parekh: Analysis of a Greedy Heuristic for Finding Small Dominating Sets in Graphs. 237-240
Maurizio Tucci, Gennaro Costagliola, Shi-Kuo Chang: A Remark on NP-Completeness of Picture Matching. 241-243
Dimitris Kavadias, Lefteris M. Kirousis, Paul G. Spirakis: The Complexity of the Reliable Connectivity Problem. 245-252
Prabhakar Ragde: Analysis of an Asynchronous PRAM Algorithm. 253-256
D. Sreenivasa Rao, John D. Provence: An Integrated Approach to Routing and Via Minimization. 257-263
Jan L. A. van de Snepscheut: Inversion of a Recursive Tree Traversal. 265-267
Coenraad Bron, Wim H. Hesselink: Smoothsort Revisited. 269-276
Lih-Hsing Hsu, Rong-Hong Jan, Yu-Che Lee, Chun-Nan Hung, Maw-Sheng Chern: Finding the Most Vital Edge with Respect to Minimum Spanning Tree in Weighted Graphs. 277-281
Jae Dong Yang, Yoon-Joon Lee: A Sound and Complete Query Evaluation for Implicit Predicate which is a Semantic Descriptor of Unknown Values. 283-289

Bernhard von Stengel: An Algebraic Characterization of Semantic Independence. 291-296
Davide Crippa: A Special Case of the Dynamization Problem for Least Cost Paths. 297-302
Jianer Chen: Characterizing Parallel Hierarchies by Reducibilities. 303-307
Rodney R. Howell: The Complexity of Problems Involving Structurally Bounded and Conservative Petri Nets. 309-315
Ricardo A. Baeza-Yates: Height Balance Distribution of Search Trees. 317-324
A. Bijlsma: Derivation of Logic Programs by Functional Methods. 325-332
Jean Frédéric Myoupo: Dynamic Programming on Linear Pipelines. 333-341
Michel Raynal, André Schiper, Sam Toueg: The Causal Ordering Abstraction and a Simple Way to Implement it. 343-350