Information Processing Letters, Volume 54

Volume 54, Number 1, 14 April 1995

• Stavros D. Nikolopoulos:
  Constant-Time Parallel Recognition of Split Graphs. 1-8
  
• H. Petersen:
  On Space Functions Fully Constructed by Two-Dimensional Turing Machines. 9-10
  
• Hamed Nassar:
  A Markov Model for Multibus Multiprocessor Systems Under Asynchronous Operation. 11-16
  
• Roope Kaivola:
  On Modal mu-Calculus and Büchi Tree Automata. 17-22
  
• Paul E. Dunne, Chris J. Gittings, Paul H. Leng:
  Multiprocessor Simulation Strategies with Optimal Speed-up. 23-33
  
• Irena Rusu:
  Quasi-Parity and Perfect Graphs. 35-39
  
• Mitsunori Ogihara:
  On Helping by Parity-Like Languages. 41-43
  
• Sundeep Oberoi:
  lambda_beta' - A - lambda-Calculus with a Generalized beta-Reduction Rule. 45-53
  
• David Maxwell Chickering, Dan Geiger, David Heckerman:
  On Finding a Cycle Basis with a Shortest Maximal Cycle. 55-58
  
• Ming-Yang Kao:
  Linear-Time Optimal Augmentation for Componentwise Bipartite-Completeness of Graphs. 59-63
  

Volume 54, Number 2, 28 April 1995

• Cliff B. Jones:
  Partial Functions and Logics: A Warning. 65-67
  
• Chui-Cheng Chen, Rong-Jaye Chen:
  Compact Embedding of Binary Trees Into Hyperacubes. 69-72
  
• Giorgio Ausiello, Marco Protasi:
  Local Search, Reducibility and Approximability of NP-Optimization Problems. 73-79
  
• Luis Barriga, Rassul Ayani:
  Lazy Update: An Efficient Implementation of LRU Stacks. 81-84
  
• Gene Myers:
  Approximately Matching Context-Free Languages. 85-92
  
• Horst Bunke, János Csirik:
  An Improved Algorithm for Computing the Edit Distance of Run-Length Coded Strings. 93-96
  
• Richa Agarwala, David Fernández-Baca:
  Weighted Search in the Plane. 97-100
  
• Dennis Moore, William F. Smyth:
  A Correction to ``An Optimal Algorithm to Compute all the Covers of a String''. 101-103
  
• Guozhu Dong:
  On the Index of Positive Programmed Formal Languages. 105-110
  
• Israel Cidon, Yuval Shavitt:
  Message Terminating Algorithms for Anonymous Rings of Unknown Size. 111-119
  
• George Varghese, Roger D. Chamberlain, William E. Weihl:
  Deriving Global Virtual Time Algorithms from Conservative Simulation Protocols. 121-126
  
• Mark Allen Weiss:
  A Note on Construction of Treaps and Cartesian Trees. 127
  

Volume 54, Number 3, 12 May 1995

• Teofilo F. Gonzalez:
  A Simple LP-Free Approximation Algorithm for the Minimum Weight Vertex Cover Problem. 129-131
  
• John S. Schlipf, Fred S. Annexstein, John V. Franco, Ramjee P. Swaminathan:
  On Finding Solutions for Extended Horn Formulas. 133-137
  
• Guillermo A. Alvarez, Marcelo O. Fernández:
  Efficient Management of Multiple Outstanding Timeouts. 139-145
  
• Robert Snelick, Joseph JáJá, Raghu Kacker, Gordon Lyon:
  Using Synthetic Perturbations and Statistical Screening to Assay Shared-Memory Programs. 147-153
  
• Gerhard J. Woeginger:
  Scheduling with Time-Dependent Execution Times. 155-156
  
• Robert H. Sloan:
  Four Types of Noise in Data for PAC Learning. 157-162
  
• Ravi Jain, John Werth:
  Analysis of Approximate Algorithms for Edge-Coloring Bipartite Graphs. 163-168
  
• Birgit Jenner:
  Knapsack Problems for NL. 169-174
  
• Stanislaw Gawiejnowicz, Lidia Pankowska:
  Scheduling Jobs with Varying Processing Times. 175-178
  
• Rajesh P. N. Rao:
  A Note on P-Selective Sets and Closeness. 179-185
  

Volume 54, Number 4, 26 May 1995

• Xiaokang Yu:
  A New Solution for Thue's Problem. 187-191
  
• Rossella Petreschi, Andrea Sterbini:
  Recognizing Strict 2-Threshold Graphs in O(m) Time. 193-198
  , Erratum: Inf. Process. Lett. 56(1): 65(1995)
• Henning Fernau:
  A Note on Uniformly Limited ETOL Systems with Unique Interpretation. 199-204
  
• Martin Kummer:
  A Learning-Theoretic Characterization of Classes of Recursive Functions. 205-211
  
• Ferruccio Barsi:
  Decoding Residue Codes. 213-222
  
• Satoshi Fujita:
  A Note on the Size of a Multicast Tree in Hypercubes. 223-227
  
• Massimiliano Goldwurm:
  Random Generation of Words in an Algebraic Language in Linear Binary Space. 229-233
  
• Jean-Jacques Hébrard:
  Unique Horn Renaming an Unique 2-Satisfiability. 235-239
  
• Marek Chrobak, T. H. Payne:
  A Linear-Time Algorithm for Drawing a Planar Graph on a Grid. 241-246
  
• Ashok Subramanian:
  Erratum: A Polynomial Bound on the Number of Light Cycles in an Undirected Graph. 247
  , ->Inf. Process. Lett. 53(4): 173-176(1995)

Volume 54, Number 5, 9 June 1995

• Klaus Simon:
  A Note on Lexicographic Breadt First Search for Chordal Graphs. 249-251
  
• Derek G. Corneil, Stephan Olariu, Lorna Stewart:
  A Linear Time Algorithm to Compute a Dominating Path in an AT-Free Graph. 253-257
  
• Ted Herman, Sukumar Ghosh:
  Stabilizing Phase-Clocks. 259-265
  
• Eddy Fromentin, Claude Jard, Guy-Vincent Jourdan, Michel Raynal:
  On-The-Fly Analysis of Distributed Computations. 267-274
  
• Kokichi Sugihara, Hiroshi Inagaki:
  Why is the 3D Delaunay Triangulation Difficult to Construct. 275-280
  
• Stéphane Demri:
  3-SAT=SAT for a Class of Normal Modal Logics. 281-287
  
• Kazuo Iwama, Toniann Pitassi:
  Exponential Lower Bounds for the Tree-Like Hajós Calculus. 289-294
  
• Akihiro Fujiwara, Toshimitsu Masuzawa, Hideo Fujiwara:
  An Optimal Parallel Algorithm for the Euclidean Distance Maps of 2-D Binary Images. 295-300
  
• Aart Blokhuis, Ton Kloks:
  On the Equivalence Covering Number of Splitgraphs. 301-304
  
• G. Sajith, Sanjeev Saxena:
  Corrigendum: Optimal Parallel Algorithms for Coloring Bounded Degree Graphs and Finding Maximal Independent Sets in Rooted Trees. 305
  , ->Inf. Process. Lett. 49(6): 303-308(1994)

Volume 54, Number 6, 23 June 1995

• Aldo de Luca:
  A Division Property of the Fibonacci Word. 307-312
  
• John Tromp, Jeffrey Shallit:
  Subword Complexity of a Generalized Thue-Morse Word. 313-316
  
• Vassilis Zissimopoulos:
  On the Performance Guarantee of Neural Networks for NP-Hard Optimization Problems. 317-322
  
• James P. Schmeiser, David T. Barnard:
  Producing a Top-Down Parse Order with Bottom-up Parsing. 323-326
  
• Jörg Desel, Ekkart Kindler, Tobias Vesper, Rolf Walter:
  A Simplified Proof for a Self-Stabilizing Protocol: A Game of Cards. 327-328
  
• Premkumar Vadapalli, Pradip K. Srimani:
  Trivalent Cayley Graphs for Interconnection Networks. 329-335
  
• Noga Alon, Yishay Mansour:
  epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials. 337-342
  
• François Laroussinie:
  About the Expressive Power of CTL Combinators. 343-345
  
• Bruce E. Litow:
  The Influence of Graph Structure on Generalized Dimension Exchange. 347-353
  
• Yen-Jen Oyang:
  A Tight Upper Bound of the Lumped Disk Seek Time for the Scan Disk Scheduling Policy. 355-358
  
• Ralph P. Boland, Jorge Urrutia:
  Corrigendum: Separating Collections of Points in Euclidean Spaces. 359
  , ->Inf. Process. Lett. 53(4): 177-183(1995)