Information Processing Letters, Volume 67

Volume 67, Number 1, 16 July 1998

• Michael Hanus, Salvador Lucas, Aart Middeldorp:
  Strongly Sequential and Inductively Sequential Term Rewriting Systems. 1-8
  
• Vincenzo Liberatore:
  Uniform Multipaging Reduces to Paging. 9-12
  
• Paolo Bottoni, Stefano Levialdi, Gheorghe Paun:
  Successful Visual Human-Computer Interaction is Undecidable. 13-19
  
• Wuu Yang:
  A Data-Parallel Algorithm for Minimum-Width Tree Layout. 21-28
  
• Andreas Blass, Yuri Gurevich, Vladik Kreinovich, Luc Longpré:
  A Variation on the Zero-One Law. 29-30
  
• Márcia R. Cerioli, Hazel Everett, Celina M. Herrera de Figueiredo, Sulamita Klein:
  The Homogeneous Set Sandwich Problem. 31-35
  
• Jan Johannsen:
  Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes. 37-41
  
• Uwe Waldmann:
  Extending Reduction Orderings to ACU-Compatible Reduction Orderings. 43-49
  
• Enrico Nardelli, Guido Proietti, Peter Widmayer:
  Finding the Detour-Critical Edge of a Shortest Path Between Two Nodes. 51-54
  

Volume 67, Number 2, 30 July 1998

• Annalisa De Bonis, Ugo Vaccaro:
  Improved Algorithms for Group Testing with Inhibitors. 57-64
  
• Neil C. Audsley, Alan Burns:
  On Fixed Priority Scheduling, Offsets and Co-Prime Task Periods. 65-69
  
• Michael Krivelevich, Benny Sudakov:
  Coloring Random Graphs. 71-74
  
• Jorge Castro, David Guijarro, Víctor Lavín:
  Learning Nearly Monotone k-Term DNF. 75-79
  
• José Luis Montaña, Luis Miguel Pardo:
  On Kolmogorov Complexity in the Real Turing Machine Setting. 81-86
  
• Vince Grolmusz:
  A Lower Bound for Depth-3 Circuits with MOD m Gates. 87-90
  
• Burton Rosenberg:
  Fast Nondeterministic Recognition of Context-Free Languages Using two Queues. 91-93
  
• Jan A. Bergstra, Alban Ponse:
  Kleene's Three-Valued Logic and Process Algebra. 95-103
  
• Jeffrey Mark Phillips, Abraham P. Punnen, Santosh N. Kabadi:
  A Linear Time Algorithm for the Bottleneck Traveling Salesman Problem on a Halin Graph. 105-110
  

Volume 67, Number 3, 17 August 1998

• Maxime Crochemore, Filippo Mignosi, Antonio Restivo:
  Automata and Forbidden Words. 111-117
  
• Mila E. Majster-Cederbaum, Markus Roggenbach:
  Transistion Systems from Event Structures Revisited. 119-124
  
• Refael Hassin, Shlomi Rubinstein:
  An Approximation Algorithm for the Maximum Traveling Salesman Problem. 125-130
  
• Peter Damaschke:
  Randomized Group Testing for Mutually Obscuring Defectives. 131-135
  
• Sanguthevar Rajasekaran:
  An Optimal Parallel Algorithm for Sorting Multisets. 141-143
  
• Dino Pedreschi, Salvatore Ruggieri:
  Weakest Preconditions for Pure Prolog Programs. 145-150
  
• Loon-Been Chen, I-Chen Wu:
  On the Time Complexity of Minimum and Maximum Global Snapshot Problems. 151-156
  
• Nimmagadda Chalamaiah, Badrinath Ramamurthy:
  Finding Shortest Paths in Distributed Loop Networks. 157-161
  

Volume 67, Number 4, 31 August 1998

• Martin Löbbing, Detlef Sieling, Ingo Wegener:
  Parity OBDDs Cannot be Handled Efficiently Enough. 163-168
  
• Roland Carl Backhouse:
  Pair Algebras and Galois Connections. 169-175
  
• Eric Bonabeau, Florian Hénaux:
  Self-Organizing Maps for Drawing Large Graphs. 177-184
  
• Fabio Martinelli:
  An Improvement of Algorithms for Solving Interface Equations. 185-190
  
• Satoshi Fujita:
  A Quorum Based k-Mutual Exclusion by Weighted k-Quorum Systems. 191-197
  
• G. Greco:
  Embeddings and the Trace of Finite Sets. 199-203
  
• Oded Goldreich, Johan Håstad:
  On the Complexity of Interactive Proofs with Bounded Communication. 205-214
  
• Franz Baader:
  On the Complexity of Boolean Unification. 215-220
  

Volume 67, Number 5, 15 September 1998

• Huaxiong Wang:
  On Syntactic Nuclei of Rational Languages. 221-226
  
• Frank Harary, Desh Ranjan:
  Breaking Symmetry in Complete Graphs by Orienting Edges: Asymptotic Bounds. 227-230
  
• Rainer E. Burkard, Vladimir G. Deineko:
  On the Traveling Salesman Problem with a Relaxed Monge Matrix. 231-237
  
• Hiroshi Nagamochi, Toshihide Ibaraki:
  A Note on Minimizing Submodular Functions. 239-244
  
• Salvador Lucas:
  Root-Neededness and Approximations of Neededness. 245-254
  
• Andrea Sterbini, Thomas Raschle:
  An O(n³) Time Algorithm for Recognizing Threshold Dimension 2 Graphs. 255-259
  
• George Gens, Eugene Levner:
  An Approximate Binary Search Algorithm for the Multiple-Choice Knapsack Problem. 261-265
  
• Teofilo F. Gonzalez:
  Improved Approximation Algorithms for Embedding Hyperedges in a Cycle. 267-271
  

Volume 67, Number 6, 30 September 1998

• Jorge L. Ramírez Alfonsín:
  A Special Arrangement with Minimal Number of Triangles. 273-276
  
• Giovanna Guaiana, Raphaël Meyer, Antoine Petit, Pascal Weil:
  An Extension of the Wreath Product Principle for Finite Mazurkiewicz Traces. 277-282
  
• Qian-Ping Gu, Shietung Peng:
  An Efficient Algorithm for k-Pairwise Disjoint Paths in Star Graphs. 283-287
  
• Francis C. Chu:
  Reducing Omega to Diamond W. 289-293
  
• Tomás Feder, Sunil M. Shende:
  Online Channel Allocation in FDMA Networks with Reuse Constraints. 295-302
  
• Timothy M. Chan:
  Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning. 303-304
  
• Peter Sanders:
  Random Permutations on Distributed, External and Hierarchical Memory. 305-309
  
• Kyunghee Choi, Gihyun Jung, Teageun Kim, Seunhun Jung:
  Real-Time Scheduling Algorithm for Minimizing Maximum Weighted Error with O(N log N + cN) Complexity. 311-315
  
• Ali Boroujerdi, Jeffrey K. Uhlmann:
  An Efficient Algorithm for Computing Least Cost Paths with Turn Constraints. 317-321