Information Processing Letters, Volume 45

Volume 45, Number 1, 25 January 1993

• Jens Palsberg: Normal Forms Have Partial Types. 1-3
• John F. Dillenburg, Peter C. Nelson: Improving the Efficiency of Depth-First Search by Cycle Elimination. 5-10
• Vincent A. Fischetti, Gad M. Landau, Peter H. Sellers, Jeanette P. Schmidt: Identifying Periodic Occurrences of a Template with Applications to Protein Structure. 11-18 , Corrigendum: Inf. Process. Lett. 46(3): 157(1993)
• Magnús M. Halldórsson: A Still Better Performance Guarantee for Approximate Graph Coloring. 19-23
• Kao-Chêng Lin, Maw-Sheng Chern: The Most Vital Edges in the Minimum Spanning Tree Problem. 25-31
• Jeong Uk Kim, Ho-Chang, Tag Gon Kim: Multidisk Partial Match File Design with Known Access Pattern. 33-39
• Berry Schoenmakers: A Systematic Analysis of Splaying. 41-50
• Ricardo A. Baeza-Yates, Mireille Régnier: Fast Two-Dimensional Pattern Matching. 51-57

Volume 45, Number 2, 26 February 1993

• James A. Foster: The Generic Oracle Hypothesis is False. 59-62
• David Cross, Reinhard Drefenstedt, Jörg Keller: Reduction of Network Cost and Wiring in Ranade's Butterfly Routing. 63-67
• Andrew Chin: Permutations on the Block PRAM. 69-73
• Jifeng He, C. A. R. Hoare: From Algebra to Operational Semantics. 75-80
• Slawomir Pilarski, Tiko Kameda: Simple Bounds on the Convergence Rate of an Ergodic Markov Chain. 81-87
• Frank Drewes: NP-Completeness of k-Connected Hyperedge-Replacement Languages of Order k. 89-94
• Marshall W. Bern: Approximate Closest-Point Queries in High Dimensions. 95-99
• Michael J. Fischer, Shlomo Moran, Gadi Taubenfeld: Space-Efficient Asynchronous Consensus Without Shared Memory Initialization. 101-105
• Tracy Kimbrel, Rakesh K. Sinha: A Probabilistic Algorithm for Verifying Matrix Products Using O(n²) Time and log_2 n + O(1) Random Bits. 107-110

Volume 45, Number 3, 8 March 1993

• Bin Jiang: I/O-and CPU-Optimal Recognition of Strongly Connected Components. 111-115
• Desh Ranjan, Daniela Rus: A Tool for the Analysis of Manipulation. 117-121
• Khaled Day, Anand R. Tripathi: Unidirectional Star Graphs. 123-129
• Cheng-Chia Chen, I-Peng Lin: The Computational Complexity of Satisfiability of Temporal Horn Formulas in Propositional Linear-Time Temporal Logic. 131-136
• Michael Merritt, Gadi Taubenfeld: Speeding Lamport's Fast Mutual Exclusion Algorithm. 137-142
• Maciej Liskiewicz: On the Relationship Between Deterministic Time and Deterministic Reversal. 143-146
• Nancy M. Amato: Improved Processor Bounds for Parallel Algorithms for Weighted Directed Graphs. 147-152
• Suchen H. Hsu, Richard T. Snodgrass: Optimal Block Size for Set-Valued Attributes. 153-158
• Francis Suraweera, Prabir Bhattacharya: An O(log m) Parallel Algorithm for the Minimum Spanning Tree Problem. 159-163

Volume 45, Number 4, 22 March 1993

• Marek Raczunas: Remarks on the Equivalence of c-e Structures and Petri Nets. 165-169
• Edmund Ihler, Dorothea Wagner, Frank Wagner: Modeling Hypergraphs by Graphs with the Same Mincut Properties. 171-175
• Feng-Hsu Wang, Ferng-Ching Lin: On Constructing Multiple Spanning Trees in a Hypercube. 177-183
• Y. Daniel Liang, Chongkye Rhee: Finding a Maximum Matching in a Circular-Arc Graph. 185-190
• Anastasia Analyti, Sakti Pramanik: Performance Analysis of a Main Memory Multi-Directory Hashing Technique. 191-197
• Xiaojun Shen, Qing Hu, Bin Cong, Ivan Hal Sudborough, Mike Girou, Saïd Bettayeb: The 4-Star Graph is not a Subgraph of Any Hypercube. 199-203
• Benny Chor, Eyal Kushilevitz: A Communication-Privacy Tradeoff for Modular Addition. 205-210
• David A. Rosenblueth: An Execution Mechanism for Nondeterministic, State-Oriented Programs Based on a Chart Parser. 211-217

Volume 45, Number 5, 2 April 1993

• Michael Buro: On the Maximum Length of Huffman Codes. 219-223
• Steven Cheung, Francis C. M. Lau: A Lower Bound for Permutation Routing on Two-Dimensional Bused Meshes. 225-228
• Jeremy Spinrad: Doubly Lexical Ordering of Dense 0 - 1 Matrices. 229-235
• Philipp Hanschke, Jörg Würtz: Satisfiability of the Smallest Binary Program. 237-241
• A. Bijlsma: Quasi-Boolean Equivalence. 243-247
• Roberto De Prisco, Alfredo De Santis: On Binary Search Trees. 249-253
• Jian Lu: Parallelizing Mallat Algorithm for 2-D Wavelet Transforms. 255-259
• D. T. Lee, Evanthia Papadopoulou: The All-Pairs Quickest Path Problem. 261-267
• Matthew Dickerson, Jason Shugart: A Simple Algorithm for Enumerating Longest Distances in the Plane. 269-274

Volume 45, Number 6, 16 April 1993

• Jie Wang, Jay Belanger: Honest Iteration Schemes of Randomizing Algorithms. 275-278
• Leizhen Cai: The Recognition of Union Trees. 279-283
• Fanica Gavril: An Efficiently Solvable Graph Partition Problem to Which Many Problems are Reducible. 285-290
• James F. Korsh: Counting and Randomly Generating Binary Trees. 291-294
• Eric J. Schwabe: Constant-Slowdown Simulations of Normal Hypercube Algorithms on the Butterfly Network. 295-301
• Alexander A. Razborov, Avi Wigderson: n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. 303-307
• Wen-Tsuen Chen, Kuen-Rong Hsieh: A Neural Sorting Network with O(1) Time Complexity. 309-313
• Luisa Gargano, Ugo Vaccaro, A. Vozella: Fault Tolerant Routing in the Star and Pancake Interconnection Networks. 315-320
• Somasundaram Ravindran, Alan Gibbons: Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube. 321-325