Information Processing Letters, Volume 45

Volume 45, Number 1, 25 January 1993

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

Volume 45, Number 2, 26 February 1993

• James A. Foster: The Generic Oracle Hypothesis is False. 59-62 BibTeX
• David Cross, Reinhard Drefenstedt, Jörg Keller: Reduction of Network Cost and Wiring in Ranade's Butterfly Routing. 63-67 BibTeX
• Andrew Chin: Permutations on the Block PRAM. 69-73 BibTeX
• Jifeng He, C. A. R. Hoare: From Algebra to Operational Semantics. 75-80 BibTeX
• Slawomir Pilarski, Tiko Kameda: Simple Bounds on the Convergence Rate of an Ergodic Markov Chain. 81-87 BibTeX
• Frank Drewes: NP-Completeness of k-Connected Hyperedge-Replacement Languages of Order k. 89-94 BibTeX
• Marshall W. Bern: Approximate Closest-Point Queries in High Dimensions. 95-99 BibTeX
• Michael J. Fischer, Shlomo Moran, Gadi Taubenfeld: Space-Efficient Asynchronous Consensus Without Shared Memory Initialization. 101-105 BibTeX
• 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 BibTeX

Volume 45, Number 3, 8 March 1993

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

Volume 45, Number 4, 22 March 1993

• Marek Raczunas: Remarks on the Equivalence of c-e Structures and Petri Nets. 165-169 BibTeX
• Edmund Ihler, Dorothea Wagner, Frank Wagner: Modeling Hypergraphs by Graphs with the Same Mincut Properties. 171-175 BibTeX
• Feng-Hsu Wang, Ferng-Ching Lin: On Constructing Multiple Spanning Trees in a Hypercube. 177-183 BibTeX
• Y. Daniel Liang, Chongkye Rhee: Finding a Maximum Matching in a Circular-Arc Graph. 185-190 BibTeX
• Anastasia Analyti, Sakti Pramanik: Performance Analysis of a Main Memory Multi-Directory Hashing Technique. 191-197 BibTeX
• 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 BibTeX
• Benny Chor, Eyal Kushilevitz: A Communication-Privacy Tradeoff for Modular Addition. 205-210 BibTeX
• David A. Rosenblueth: An Execution Mechanism for Nondeterministic, State-Oriented Programs Based on a Chart Parser. 211-217 BibTeX

Volume 45, Number 5, 2 April 1993

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

Volume 45, Number 6, 16 April 1993

• Jie Wang, Jay Belanger: Honest Iteration Schemes of Randomizing Algorithms. 275-278 BibTeX
• Leizhen Cai: The Recognition of Union Trees. 279-283 BibTeX
• Fanica Gavril: An Efficiently Solvable Graph Partition Problem to Which Many Problems are Reducible. 285-290 BibTeX
• James F. Korsh: Counting and Randomly Generating Binary Trees. 291-294 BibTeX
• Eric J. Schwabe: Constant-Slowdown Simulations of Normal Hypercube Algorithms on the Butterfly Network. 295-301 BibTeX
• 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 BibTeX
• Wen-Tsuen Chen, Kuen-Rong Hsieh: A Neural Sorting Network with O(1) Time Complexity. 309-313 BibTeX
• Luisa Gargano, Ugo Vaccaro, A. Vozella: Fault Tolerant Routing in the Star and Pancake Interconnection Networks. 315-320 BibTeX
• Somasundaram Ravindran, Alan Gibbons: Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube. 321-325 BibTeX