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

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

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

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

Achim Schweikard: Trigonometric Polynomials with Simple Roots. 231-236 BibTeX
Abhay K. Parekh: Analysis of a Greedy Heuristic for Finding Small Dominating Sets in Graphs. 237-240 BibTeX
Maurizio Tucci, Gennaro Costagliola, Shi-Kuo Chang: A Remark on NP-Completeness of Picture Matching. 241-243 BibTeX
Dimitris Kavadias, Lefteris M. Kirousis, Paul G. Spirakis: The Complexity of the Reliable Connectivity Problem. 245-252 BibTeX
Prabhakar Ragde: Analysis of an Asynchronous PRAM Algorithm. 253-256 BibTeX
D. Sreenivasa Rao, John D. Provence: An Integrated Approach to Routing and Via Minimization. 257-263 BibTeX
Jan L. A. van de Snepscheut: Inversion of a Recursive Tree Traversal. 265-267 BibTeX
Coenraad Bron, Wim H. Hesselink: Smoothsort Revisited. 269-276 BibTeX
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 BibTeX
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 BibTeX

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