Table of contents for issues of Information Processing Letters

Last update: Sat Oct 14 13:29:30 MDT 2017                Valid HTML 3.2!

Volume 1, Number 4, June ??, 1972
Volume 6, Number 5, October ??, 1977
Volume 7, Number 6, October ??, 1978
Volume 8, Number 2, February 15, 1979
Volume 8, Number 3, March 15, 1979
Volume 8, Number 4, April 30, 1979
Volume 9, Number 3, October 5, 1979
Volume 9, Number 5, December 16, 1979
Volume 10, Number 1, February 12, 1980
Volume 10, Number 2, March 18, 1980
Volume 10, Number 3, April 18, 1980
Volume 10, Number 4--5, July 5, 1980
Volume 11, Number 1, August 29, 1980
Volume 11, Number 2, October ??, 1980
Volume 11, Number 3, November 18, 1980
Volume 11, Number 4--5, December 12, 1980
Volume 12, Number 1, February 13, 1981
Volume 12, Number 2, April 13, 1981
Volume 12, Number 3, June 13, 1981
Volume 12, Number 4, August 13, 1981
Volume 12, Number 5, October 13, 1981
Volume 13, Number 1, October ??, 1981
Volume 13, Number 2, November 13, 1981
Volume 13, Number 3, December 13, 1981
Volume 13, Number 4--5, End ??, 1981
Volume 14, Number 1, March 27, 1982
Volume 14, Number 2, April 20, 1982
Volume 14, Number 3, May 16, 1982
Volume 14, Number 4, June 13, 1982
Volume 14, Number 5, July 23, 1982
Volume 15, Number 1, August 19, 1982
Volume 15, Number 2, September 6, 1982
Volume 15, Number 3, October 11, 1982
Volume 15, Number 4, October 31, 1982
Volume 15, Number 5, December 10, 1982
Volume 16, Number 1, January 24, 1983
Volume 16, Number 2, February 26, 1983
Volume 16, Number 3, April 15, 1983
Volume 16, Number 4, May 13, 1983
Volume 16, Number 5, June 10, 1983
Volume 17, Number 1, July 19, 1983
Volume 17, Number 2, August 24, 1983
Volume 17, Number 3, October 5, 1983
Volume 17, Number 4, November 8, 1983
Volume 17, Number 5, December 15, 1983
Volume 18, Number 1, January 20, 1984
Volume 18, Number 2, February 28, 1984
Volume 18, Number 3, March 30, 1984
Volume 18, Number 4, May 14, 1984
Volume 18, Number 5, June 18, 1984
Volume 19, Number 1, July 26, 1984
Volume 19, Number 2, August 31, 1984
Volume 19, Number 3, October 19, 1984
Volume 19, Number 4, November 12, 1984
Volume 19, Number 5, November 26, 1984
Volume 20, Number 1, January 2, 1985
Volume 20, Number 2, February 15, 1985
Volume 20, Number 3, April 8, 1985
Volume 20, Number 4, May 10, 1985
Volume 20, Number 5, June 12, 1985
Volume 21, Number 1, July 10, 1985
Volume 21, Number 2, August 16, 1985
Volume 21, Number 3, September 5, 1985
Volume 21, Number 4, October 7, 1985
Volume 21, Number 5, November 18, 1985
Volume 22, Number 1, January 2, 1986
Volume 22, Number 2, January 18, 1986
Volume 22, Number 3, March 3, 1986
Volume 22, Number 4, April 17, 1986
Volume 22, Number 5, April ??, 1986
Volume 22, Number 6, May 30, 1986
Volume 23, Number 1, July 20, 1986
Volume 23, Number 2, August 20, 1986
Volume 23, Number 3, October 22, 1986
Volume 23, Number 4, November 8, 1986
Volume 23, Number 5, November 24, 1986
Volume 23, Number 6, December 3, 1986
Volume 24, Number 1, January 15, 1987
Volume 24, Number 2, January 30, 1987
Volume 24, Number 3, February 13, 1987
Volume 24, Number 4, March ??, 1987
Volume 24, Number 5, March 16, 1987
Volume 24, Number 6, April 6, 1987
Volume 25, Number 1, April 20, 1987
Volume 25, Number 2, May 6, 1987
Volume 25, Number 3, May 29, 1987
Volume 25, Number 4, June 17, 1987
Volume 25, Number 5, July 10, 1987
Volume 25, Number 6, July 26, 1987
Volume 26, Number 1, September 15, 1987
Volume 26, Number 2, October 19, 1987
Volume 26, Number 3, November 23, 1987
Volume 26, Number 4, December 4, 1987
Volume 26, Number 5, January 11, 1988
Volume 26, Number 6, January 25, 1988
Volume 27, Number 1, February 15, 1988
Volume 27, Number 2, February 29, 1988
Volume 27, Number 3, March 25, 1988
Volume 27, Number 4, April 8, 1988
Volume 27, Number 5, April 28, 1988
Volume 27, Number 6, May 13, 1988
Volume 28, Number 1, May 30, 1988
Volume 28, Number 2, June 24, 1988
Volume 28, Number 3, July 4, 1988
Volume 28, Number 4, July 29, 1988
Volume 28, Number 5, August 12, 1988
Volume 28, Number 6, August 29, 1988
Volume 29, Number 1, September 15, 1988
Volume 29, Number 2, September 30, 1988
Volume 29, Number 3, October 26, 1988
Volume 29, Number 4, November 12, 1988
Volume 29, Number 5, November 24, 1988
Volume 29, Number 6, December 8, 1988
Volume 30, Number 1, January 16, 1989
Volume 30, Number 2, January 30, 1989
Volume 30, Number 3, February 13, 1989
Volume 30, Number 4, February 27, 1989
Volume 30, Number 5, March 13, 1989
Volume 30, Number 6, March 28, 1989
Volume 31, Number 1, April ??, 1989
Volume 31, Number 2, April 26, 1989
Volume 31, Number 3, May 8, 1989
Volume 31, Number 4, May 22, 1989
Volume 31, Number 5, June 12, 1989
Volume 31, Number 6, June 19, 1989
Volume 32, Number 1, July 3, 1989
Volume 32, Number 2, July 24, 1989
Volume 32, Number 3, August 24, 1989
Volume 32, Number 4, September 1, 1989
Volume 32, Number 5, September 22, 1989
Volume 32, Number 6, October 3, 1989
Volume 33, Number 1, October 27, 1989
Volume 33, Number 2, November 10, 1989
Volume 33, Number 3, November 30, 1989
Volume 33, Number 4, December 21, 1989
Volume 34, Number 5, May 7, 1990
Volume 35, Number 6, September 15, 1990
Volume 38, Number 4, May 31, 1991
Volume 40, Number 5, December 13, 1991
Volume 43, Number 5, October 5, 1992
Volume 47, Number 3, September 14, 1993


Information Processing Letters
Volume 1, Number 4, June ??, 1972

                   R. L. Graham   An efficient algorithm for determining
                                  the convex hull of a finite planar set   132--133


Information Processing Letters
Volume 6, Number 5, October ??, 1977

                      T. D. Bui   On an $L$-stable method for stiff
                                  differential equations . . . . . . . . . 158--161


Information Processing Letters
Volume 7, Number 6, October ??, 1978

                       A. Bykat   Convex hull of a finite set of points in
                                  two dimensions . . . . . . . . . . . . . 296--298


Information Processing Letters
Volume 8, Number 2, February 15, 1979

                   J. M. Morris   A starvation-free solution to the mutual
                                  exclusion problem  . . . . . . . . . . . 76--80

Information Processing Letters
Volume 8, Number 3, March 15, 1979

              Bengt Aspvall and   
           Michael F. Plass and   
            Robert Endre Tarjan   A linear-time algorithm for testing the
                                  truth of certain quantified Boolean
                                  formulas . . . . . . . . . . . . . . . . 121--123

Information Processing Letters
Volume 8, Number 4, April 30, 1979

                 Alain Fournier   Comments on convex hull of a finite set
                                  of points in two dimensions [Inform.
                                  Process. Lett. \bf 7 (1978), no. 6,
                                  296--298; MR 80b:68041]  . . . . . . . . 173--173
                      T. D. Bui   Erratum: ``On an $L$-stable method for
                                  stiff differential equations'' . . . . . 218--218


Information Processing Letters
Volume 9, Number 3, October 5, 1979

            Charles J. Colbourn   The complexity of symmetrizing matrices  108--109
            F. Dévai and   
           T. Szendrényi   Comments on convex hull of a finite set
                                  of points in two dimensions  . . . . . . 141--142

Information Processing Letters
Volume 9, Number 5, December 16, 1979

                   A. M. Andrew   Another efficient algorithm for convex
                                  hulls in two dimensions  . . . . . . . . 216--219


Information Processing Letters
Volume 10, Number 1, February 12, 1980

           Michael J. C. Gordon   The denotational semantics of sequential
                                  machines . . . . . . . . . . . . . . . . 1--3
               H. Olivié   On the relationship between son-trees
                                  and symmetric binary $B$-trees . . . . . 4--8
        V. J. Rayward-Smith and   
                    R. N. Rolph   Finding Linear and Circular Sequences of
                                  Minimal and Maximal Total Adjacency  . . 9--13
             Peter Honeyman and   
          Richard E. Ladner and   
             Mihalis Yannakakis   Testing the universal instance
                                  assumption . . . . . . . . . . . . . . . 14--19
                     Ashoke Deb   Conflict-free access of arrays --- a
                                  counter example  . . . . . . . . . . . . 20--20
       Miros\law Truszczy\'nski   Once more on storage for consecutive
                                  retrieval  . . . . . . . . . . . . . . . 21--24
         Leslie M. Goldschlager   A space efficient algorithm for the
                                  monotone planar circuit value problem    25--27
                 Errol L. Lloyd   List Scheduling Bounds for UET Systems
                                  with Resources . . . . . . . . . . . . . 28--31
                  Carlo Zaniolo   Mixed transitivity for functional and
                                  multivalued dependencies in database
                                  relations  . . . . . . . . . . . . . . . 32--34
                      T. D. Bui   A note on an improved bisection
                                  algorithm  . . . . . . . . . . . . . . . 35--36
     Daniel D. K. D. B. Sleator   A $2.5$ times optimal algorithm for
                                  packing in two dimensions  . . . . . . . 37--40
               Dilip V. Sarwate   A note on: ``Universal classes of hash
                                  functions'' [J. Comput. System Sci. \bf
                                  18 (1979), no. 2, 143--154; MR
                                  80f:68110a] by J. L. Carter and M. N.
                                  Wegman . . . . . . . . . . . . . . . . . 41--45

Information Processing Letters
Volume 10, Number 2, March 18, 1980

                 Bruce Anderson   Encoded Pointers --- an Interesting
                                  Data-Structure for Modern SIL's  . . . . 47--50
            Jan van Leeuwen and   
                    Derick Wood   Dynamization of decomposable searching
                                  problems . . . . . . . . . . . . . . . . 51--56
  V. K. Sabel\cprimefel\cprimed   The logic-termal equivalence is
                                  polynomial-time decidable  . . . . . . . 57--62
                  Solomon Passy   Structured programs for Turing machines  63--67
           Thomas C. Wilson and   
                  Joseph Shortt   An $O(\log n)$ algorithm for computing
                                  general order-$k$ Fibonacci numbers  . . 68--75
                 Frank M. Liang   A lower bound for on-line bin packing    76--79
                Manuel Blum and   
           Ashok K. Chandra and   
                 Mark N. Wegman   Equivalence of free Boolean graphs can
                                  be decided probabilistically in
                                  polynomial time  . . . . . . . . . . . . 80--82
      Paul M. B. Vitányi   Achievable high scores of
                                  $\varepsilon$-moves and running times in
                                  DPDA computations  . . . . . . . . . . . 83--86
                 Nicola Santoro   Extending the Four Russians' Bound to
                                  General Matrix Multiplication  . . . . . 87--88
                Hanan Samet and   
                     Leo Marcus   Purging in an Equality Data Base . . . . 89--95
              Mordechai Ben-Ari   A simplified proof that regular
                                  resolution is exponential  . . . . . . . 96--98
        Alexandre Brandwajn and   
                      Rene Joly   A scheme for a fault-tolerant virtual
                                  memory . . . . . . . . . . . . . . . . . 99--103
                 Frank G. Pagan   On the generation of compilers from
                                  language definitions . . . . . . . . . . 104--107
                    M. Jazayeri   An improvement in the iterative data
                                  flow analysis algorithm  . . . . . . . . 108--110

Information Processing Letters
Volume 10, Number 3, April 18, 1980

                R. K. Arora and   
                     S. P. Rana   Analysis of the Module Assignment
                                  Problem in Distributed Computing Systems
                                  with Limited Storage . . . . . . . . . . 111--115
                    O. Watanabe   Another application of recursion
                                  introduction . . . . . . . . . . . . . . 116--119
         Peter J. L. Wallis and   
           Bernard W. Silverman   Efficient Implementation of the Ada
                                  Overloading Rules  . . . . . . . . . . . 120--123
                     C. Hemerik   Formal derivation of a list processing
                                  program  . . . . . . . . . . . . . . . . 124--126
           David G. Kirkpatrick   A note on Delaunay and optimal
                                  triangulations . . . . . . . . . . . . . 127--128
          Patrick Shen-Pei Wang   Some new results on isotonic array
                                  grammars . . . . . . . . . . . . . . . . 129--131
            Peter van Emde Boas   On the $\Omega(n\log n)$ lower bound for
                                  convex hull and maximal vector
                                  determination  . . . . . . . . . . . . . 132--136
           Wojciech Cellary and   
                   Daniel Mayer   A simple model of query scheduling in
                                  distributed data base systems  . . . . . 137--147
                  J. A. Barnden   A characterization of systems derived
                                  from terminating concurrent histories    148--152
                   Ludwik Czaja   Parallel System Schemas and Their
                                  Relation to Automata . . . . . . . . . . 153--158
            J. L. W. I. Kessels   The readers and writers problem avoided  159--162
                 M. van der Nat   A Fast Sorting Algorithm, a Hybrid of
                                  Distributive and Merge Sorting . . . . . 163--167
                   A. M. Andrew   Corrigendum: ``Another efficient
                                  algorithm for convex hulls in two
                                  dimensions'' (Inform. Process. Lett. \bf
                                  9 (1979), no. 5, 216--219) . . . . . . . 168--168

Information Processing Letters
Volume 10, Number 4--5, July 5, 1980

            Robert Melville and   
                    David Gries   Controlled Density Sorting . . . . . . . 169--172
               Alan A. Bertossi   On the complexity of scheduling jobs on
                                  dedicated resources to minimize set-up
                                  costs  . . . . . . . . . . . . . . . . . 173--177
        Aviezri S. Fraenkel and   
                   Yaacov Yesha   Complexity of solving algebraic
                                  equations  . . . . . . . . . . . . . . . 178--179
                  F. Luccio and   
                     S. Mazzone   A cryptosystem for multiple
                                  communication  . . . . . . . . . . . . . 180--183
            Thomas Lengauer and   
               Robert E. Tarjan   The space complexity of pebble games on
                                  trees  . . . . . . . . . . . . . . . . . 184--188
               Arthur M. Farley   Levelling Terrain Trees: a Transshipment
                                  Problem  . . . . . . . . . . . . . . . . 189--192
                    M. Broy and   
                     M. Wirsing   Program development: from enumeration to
                                  backtracking . . . . . . . . . . . . . . 193--197
               F. W. Burton and   
                    G. N. Lewis   A robust variation of interpolation
                                  search . . . . . . . . . . . . . . . . . 198--201
                   Carla Savage   Maximum matchings and trees  . . . . . . 202--205
                R. W. Doran and   
                   L. K. Thomas   Variants of the software solution to
                                  mutual exclusion . . . . . . . . . . . . 206--208
           Mark H. Overmars and   
                Jan van Leeuwen   Further comments on A. Bykat's convex
                                  hull algorithm: ``Convex hull of a
                                  finite set of points in two dimensions''
                                  [Inform. Process. Lett. \bf 7 (1978),
                                  no. 6, 296--298; MR 80b:68041] . . . . . 209--212
                Henk Meijer and   
                   Selim G. Akl   The Design and Analysis of a New Hybrid
                                  Sorting Algorithm  . . . . . . . . . . . 213--218
             Akira Nakamura and   
                 Katsushi Inoue   A remark on two-dimensional finite
                                  automata: ``Some properties of
                                  two-dimensional on-line tessellation
                                  acceptors'' [Inform. Sci. \bf 13 (1977),
                                  no. 2, 95--121; MR 80e:68143]  . . . . . 219--222
             A. Ehrenfeucht and   
                   G. Rozenberg   On the emptiness of the intersection of
                                  two D0S languages problem  . . . . . . . 223--225
                K. M. Chung and   
                  F. Luccio and   
                     C. K. Wong   A new permutation algorithm for bubble
                                  memories . . . . . . . . . . . . . . . . 226--230
          Corrado Böhm and   
            Antonio Mach\`i and   
             Giovanna Sontacchi   Complexity bounds for equivalence and
                                  isomorphism of Latin squares . . . . . . 231--233
                   Ludwik Czaja   Deadlock and Fairness in Parallel
                                  Schemas: a Set-Theoretic
                                  Characterization and Decision Problems   234--239
               Kellogg S. Booth   Lexicographically least circular
                                  substrings . . . . . . . . . . . . . . . 240--242
              Peter Buneman and   
                      Leon Levy   The Towers of Hanoi problem  . . . . . . 243--244
             Katsushi Inoue and   
                 Itsuo Takanami   A note on decision problems for
                                  three-way two-dimensional finite
                                  automata . . . . . . . . . . . . . . . . 245--248


Information Processing Letters
Volume 11, Number 1, August 29, 1980

         Edsger W. Dijkstra and   
                 C. S. Scholten   Termination detection for diffusing
                                  computations . . . . . . . . . . . . . . 1--4
       W\lodzimierz Dobosiewicz   An Efficient Variation of Bubble Sort    5--6
           D. C. S. Allison and   
                     M. T. Noga   Selection by distributive partitioning   7--8
                Tomasz Krawczyk   Error correction by mutational grammars  9--15
            Kabekode V. S. Bhat   On the complexity of testing a graph for
                                  $n$-cube . . . . . . . . . . . . . . . . 16--19
                  Jan Grabowski   The decidability of persistence for
                                  vector addition systems  . . . . . . . . 20--23
                Michael C. Loui   A note on the pebble game  . . . . . . . 24--26
                      J. D. Day   On the internal $S$-stability of
                                  Rosenbrock methods . . . . . . . . . . . 27--30
                      J. D. Day   Comments on: ``On an $L$-stable method
                                  for stiff differential equations''
                                  [Inform. Process. Lett. 6 (1977), no. 5,
                                  158--161; MR \bf 56 #10015] by T. D. Bui 31--32
                      G. Loizou   On a cycle finding algorithm . . . . . . 33--36
                 Donna J. Brown   An improved BL lower bound . . . . . . . 37--39
                 J. L. Peterson   A note on colored Petri nets . . . . . . 40--43
                  L. G. Valiant   Computing multivariate polynomials in
                                  parallel . . . . . . . . . . . . . . . . 44--45
                    R. P. Brent   On the area of binary tree layouts . . . 46--48
                Charles R. Dyer   A fast parallel algorithm for the
                                  closest pair problem . . . . . . . . . . 49--52
                    Luc Devroye   A note on finding convex hulls via
                                  maximal vectors  . . . . . . . . . . . . 53--56
                    E. L. Lloyd   Errata: ``List scheduling bounds for UET
                                  systems with resources'' [Inform.
                                  Process. Lett. \bf 10 (1980), no. 1,
                                  28--31; MR 81a:68042]  . . . . . . . . . 57--57
             J. van Leeuwen and   
                        D. Wood   Errata: ``List scheduling bounds for UET
                                  systems with resources'' [Inform.
                                  Process. Lett. \bf 10 (1980), no. 1,
                                  28--31; MR 81a:68042]  . . . . . . . . . 57--57

Information Processing Letters
Volume 11, Number 2, October ??, 1980

               Lech Banachowski   A complement to Tarjan's result about
                                  the lower bound on the complexity of the
                                  set union problem  . . . . . . . . . . . 59--65
           Friedrich J. Urbanek   An $O(\log n)$ algorithm for computing
                                  the $n$th element of the solution of a
                                  difference equation  . . . . . . . . . . 66--67
                David Gries and   
                     Gary Levin   Computing Fibonacci numbers (and
                                  similarly defined functions) in log time 68--69
              Jürgen Ebert   A note on odd and even factors of
                                  undirected graphs  . . . . . . . . . . . 70--72
                Lishing Liu and   
                    Alan Demers   An algorithm for testing lossless join
                                  property in relational databases . . . . 73--76
        Franco P. Preparata and   
              Jean E. Vuillemin   Area-Time Optimal VLSI Networks for
                                  Multiplying Matrices . . . . . . . . . . 77--80
                K. M. Chung and   
                  F. Luccio and   
                     C. K. Wong   Minimum number of steps for permutation
                                  in a bubble memory . . . . . . . . . . . 81--83
                  Andrew C. Yao   A Note on the Analysis of Extendible
                                  Hashing  . . . . . . . . . . . . . . . . 84--86
                        M. Broy   Transformational Semantics for
                                  Concurrent Programs  . . . . . . . . . . 87--91
         Robert B. Johnson, Jr.   The complexity of a VLSI adder . . . . . 92--93
                  J. Calmet and   
                        R. Loos   An improvement of Rabin's probabilistic
                                  algorithm for generating irreducible
                                  polynomials over GF($p$) . . . . . . . . 94--95
        Charles J. Colbourn and   
               Brendan D. McKay   A correction to Colbourn's paper on the
                                  complexity of matrix symmetrizability:
                                  ``The complexity of symmetrizing
                                  matrices'' [Inform. Process. Lett. \bf 9
                                  (1979), no. 3, 108--109; MR 81a:68045]   96--97
            Paris C. Kanellakis   On the computational complexity of
                                  cardinality constraints in relational
                                  databases  . . . . . . . . . . . . . . . 98--101
                   E. Luque and   
                      A. Ripoll   Tuning Architecture via Microprogramming 102--109
                       E. Leiss   A note on a signature system based on
                                  probabilistic logic  . . . . . . . . . . 110--113

Information Processing Letters
Volume 11, Number 3, November 18, 1980

         Joseph Y.-T. Leung and   
                  M. L. Merrill   A note on preemptive scheduling of
                                  periodic, real-time tasks  . . . . . . . 115--118
                   J. M. Robson   Storage allocation is NP-hard  . . . . . 119--125
                     David Avis   Comments on a lower bound for convex
                                  hull determination: ``On the
                                  $\Omega(n\log n)$ lower bound for convex
                                  hull and maximal vector determination''
                                  by van Emde Boas [Inform. Process. Lett.
                                  \bf 10(3), 18 April 1980, pp. 132--136]  126--126
                  Arnaldo Moura   A note on grammatical covers . . . . . . 127--129
               T. A. Bailey and   
                   R. G. Dromey   Fast string searching by finding subkeys
                                  in subtext . . . . . . . . . . . . . . . 130--133
               Francesco Romani   Shortest-path problem is not harder than
                                  matrix multiplication  . . . . . . . . . 134--136
                       H. Erkio   Internal merge sorting with delayed
                                  selection  . . . . . . . . . . . . . . . 137--140
                  N. Dershowitz   The Schorr--Waite marking algorithm
                                  revisited  . . . . . . . . . . . . . . . 141--143
                   E. B. Kinber   On inclusion problem for deterministic
                                  multitape automata . . . . . . . . . . . 144--146

Information Processing Letters
Volume 11, Number 4--5, December 12, 1980

                        A. Laut   Safe procedural implementations of
                                  algebraic types  . . . . . . . . . . . . 147--151
               J. Paredaens and   
                    F. Ponsaert   Grant levels in an authorization
                                  mechanism  . . . . . . . . . . . . . . . 152--155
           Greg N. Frederickson   Probabilistic analysis for simple one-
                                  and two-dimensional bin packing
                                  algorithms . . . . . . . . . . . . . . . 156--161
            Oscar H. Ibarra and   
               Shlomo Moran and   
                Louis E. Rosier   A note on the parallel complexity of
                                  computing the rank of order $n$ matrices 162--162
                   D. R. Hanson   Code improvement via lazy evaluation . . 163--167
                J. H. ter Bekke   Convertibility in databases  . . . . . . 168--171
             Alberto Pettorossi   Derivation of an $O(k^2\,\log n)$
                                  algorithm for computing order-$k$
                                  Fibonacci numbers from the $O(k^3\,\log
                                  n)$ matrix multiplication method . . . . 172--179
                 M. H. Williams   Cubic map configurations . . . . . . . . 180--185
                 M. H. Williams   Batch sizes for the batching method of
                                  colouring planar maps  . . . . . . . . . 186--189
      Mila E. Majster-Cederbaum   A simple relation between relational and
                                  predicate transformer semantics for
                                  nondeterministic programs  . . . . . . . 190--192
         Rossella Petreschi and   
                  Bruno Simeone   A switching algorithm for the solution
                                  of quadratic Boolean equations . . . . . 193--198
                R. K. Arora and   
                     S. P. Rana   Heuristic algorithms for process
                                  assignment in distributed computing
                                  systems  . . . . . . . . . . . . . . . . 199--203
                   Hiroya Kawai   A formal system for parallel programs in
                                  discrete time and space  . . . . . . . . 204--210
                  J. ten Hoopen   Consecutive retrieval with redundancy:
                                  an optimal linear and an optimal cyclic
                                  arrangement and their storage space
                                  requirements . . . . . . . . . . . . . . 211--217
              Peter Kandzia and   
             Margret Mangelmann   On covering Boyce-Codd normal forms  . . 218--223
                  Seppo Pajunen   On two theorems of Lenstra . . . . . . . 224--228
           Alfons J. Jammel and   
             Helmut G. Stiegler   On expected costs of deadlock detection  229--231


Information Processing Letters
Volume 12, Number 1, February 13, 1981

                 S. Mauceri and   
                     A. Restivo   A family of codes commutatively
                                  equivalent to prefix codes . . . . . . . 1--4
      Krzysztof Dudzi\'nski and   
                  Andrzej Dydek   On a Stable Minimum Storage Merging
                                  Algorithm  . . . . . . . . . . . . . . . 5--8
           Eugene L. Lawler and   
              Charles U. Martel   Scheduling Periodically Occurring Tasks
                                  on Multiple Processors . . . . . . . . . 9--12
                    C. Choffrut   A closure property of deterministic
                                  context-free languages . . . . . . . . . 13--16
                  Nai Kuan Tsao   The numerical instability of Bini's
                                  algorithm  . . . . . . . . . . . . . . . 17--19
                Harold N. Gabow   A linear-time recognition algorithm for
                                  interval dags  . . . . . . . . . . . . . 20--22
         Dorothy E. Denning and   
              Fred B. Schneider   Master keys for group sharing  . . . . . 23--25
              Eric C. R. Hehner   Bunch theory: a simple set theory for
                                  computer science . . . . . . . . . . . . 26--30
               S. H. Whitesides   An algorithm for finding clique cut-sets 31--32
                    P. Hell and   
              D. G. Kirkpatrick   On generalized matching problems . . . . 33--35
                  M. Bruynooghe   Solving combinatorial search problems by
                                  intelligent backtracking . . . . . . . . 36--39
                 Errol L. Lloyd   Coffman--Graham scheduling of UET task
                                  systems with $0$-$1$ resources . . . . . 40--45
                    S. Ceri and   
                   G. Pelagatti   An upper bound on the number of
                                  execution nodes for a distributed join   46--48
           Mark H. Overmars and   
                Jan van Leeuwen   Some principles for dynamizing
                                  decomposable searching problems  . . . . 49--53 (or 49--54??)

Information Processing Letters
Volume 12, Number 2, April 13, 1981

             M. Hatzopoulos and   
                  J. G. Kollias   Optimal policy for database backup and
                                  recovery . . . . . . . . . . . . . . . . 55--58
                  D. M. Harland   Concurrency in a language employing
                                  messages . . . . . . . . . . . . . . . . 59--62
        Ingemar Ingemarsson and   
                     C. K. Wong   A user authentication scheme for shared
                                  data based on a trap-door one-way
                                  function . . . . . . . . . . . . . . . . 63--67
                  J. J. Pansiot   The Morse sequence and iterated
                                  morphisms  . . . . . . . . . . . . . . . 68--70
                 A. Borodin and   
               L. J. Guibas and   
                N. A. Lynch and   
                      A. C. Yao   Efficient searching using partial
                                  ordering . . . . . . . . . . . . . . . . 71--75
                  C. P. Schnorr   How many polynomials can be approximated
                                  faster than they can be evaluated? . . . 76--78
                   Joxan Jaffar   Presburger arithmetic with array
                                  segments . . . . . . . . . . . . . . . . 79--82
            David Steinberg and   
                  Michael Rodeh   A layout for the shuffle-exchange
                                  network with $\Theta(N^2\log N)$ area    83--88
                 Yossi Shiloach   Another look at the degree constrained
                                  subgraph problem . . . . . . . . . . . . 89--92
              Kurt Mehlhorn and   
               Mark H. Overmars   Optimal dynamization of decomposable
                                  searching problems . . . . . . . . . . . 93--98
               Mark H. Overmars   General methods for ``all elements'' and
                                  ``all pairs'' problems . . . . . . . . . 99--102
                  Silvio Micali   Two-way deterministic finite automata
                                  are exponentially more succinct than
                                  sweeping automata  . . . . . . . . . . . 103--105
                   Martin Tompa   An extension of Savitch's theorem to
                                  small space bounds . . . . . . . . . . . 106--108
               R. Petreschi and   
                     B. Simeone   Erratum: ``A switching algorithm for the
                                  solution of quadratic Boolean
                                  equations''  . . . . . . . . . . . . . . 109--109

Information Processing Letters
Volume 12, Number 3, June 13, 1981

                Bruno Courcelle   The simultaneous accessibility of two
                                  configurations of two equivalent DPDAs   111--114
                 G. L. Peterson   Myths about the mutual exclusion problem 115--116
                  W. Leland and   
                  R. Finkel and   
                    Li Qiao and   
                 M. Solomon and   
                         L. Uhr   High density graphs for processor
                                  interconnection  . . . . . . . . . . . . 117--120
                 Ronald V. Book   The undecidability of a word problem: on
                                  a conjecture of Strong,
                                  Maggiolo-Schettini and Rosen . . . . . . 121--122
                Gerhard Lischke   Two types of properties for complexity
                                  measures . . . . . . . . . . . . . . . . 123--126
               Reinhard Wilhelm   A modified tree-to-tree correction
                                  problem  . . . . . . . . . . . . . . . . 127--132
           Robert J. Fowler and   
        Michael S. Paterson and   
             Steven L. Tanimoto   Optimal packing and covering in the
                                  plane are NP-complete  . . . . . . . . . 133--137
             Jerzy W. Jaromczyk   Linear decision trees are too weak for
                                  convex hull problem  . . . . . . . . . . 138--141
            Alberto Bertoni and   
                Giancarlo Mauri   On Efficient Computation of the
                                  Coefficients of Some Polynomials with
                                  Applications to Some Enumeration
                                  Problems . . . . . . . . . . . . . . . . 142--145
                    W. Erni and   
                     R. Lapsien   On the time and tape complexity of weak
                                  unification  . . . . . . . . . . . . . . 146--150
               P. Ancilotti and   
                       M. Boari   Information Streams Sharing a Finite
                                  Buffer: Protection Problems  . . . . . . 151--159

Information Processing Letters
Volume 12, Number 4, August 13, 1981

        Franco P. Preparata and   
             Kenneth J. Supowit   Testing a simple polygon for
                                  monotonicity . . . . . . . . . . . . . . 161--164
                  C. M. Eastman   Optimal bucket size for nearest neighbor
                                  searching in $k$-$d$ trees . . . . . . . 165--167
             M. H. Overmars and   
                 J. van Leeuwen   Worst-case optimal insertion and
                                  deletion methods for decomposable
                                  searching problems . . . . . . . . . . . 168--173
                     C. Frougny   Simple deterministic NTS languages . . . 174--178
                      H. Meijer   A note on ``A cryptosystem for multiple
                                  communication'' [Inform. Process. Lett.
                                  \bf 10(4--5), 5 July 1980, pp. 180--183] 179--181
                  M. E. Hellman   Another cryptanalytic attack on ``A
                                  cryptosystem for multiple
                                  communication'' [Inform. Process. Lett.
                                  \bf 10(4--5), 5 July 1980, pp. 180--183] 182--183
                 T. Ottmann and   
                 A. Salomaa and   
                        D. Wood   Sub-regular grammar forms  . . . . . . . 184--187
                 Ichir\=o Semba   Generation of all the balanced
                                  parenthesis strings in lexicographical
                                  order  . . . . . . . . . . . . . . . . . 188--192
                   Aldo de Luca   A combinatorial property of the
                                  Fibonacci words  . . . . . . . . . . . . 193--195
            E. C. R. Hehner and   
             R. K. Shyamasundar   An implementation of $P$ and $V$ . . . . 196--198
                   D. Maier and   
                 S. C. Salveter   Hysterical $B$-trees . . . . . . . . . . 199--202
  Christos H. Papadimitriou and   
             Mihalis Yannakakis   On minimal Eulerian graphs . . . . . . . 203--205
                  Masao Iri and   
               Kazuo Murota and   
                Shouichi Matsui   Linear-Time Approximation Algorithms for
                                  Finding the Minimum-Weight Perfect
                                  Matching on a Plane  . . . . . . . . . . 206--209

Information Processing Letters
Volume 12, Number 5, October 13, 1981

                  J. Mauney and   
                  C. N. Fischer   An improvement to immediate error
                                  detection in Strong LL(1) parsers  . . . 211--212
          Lloyd K. Konneker and   
                Yaakov L. Varol   A note on heuristics for dynamic
                                  organization of data structures  . . . . 213--216
                        M. Snir   On the complexity of simplifying
                                  quadratic forms  . . . . . . . . . . . . 217--220
               David M. Harland   On Facilities for Interprocess
                                  Communication  . . . . . . . . . . . . . 221--226
            Oscar H. Ibarra and   
               Shlomo Moran and   
                Louis E. Rosier   Probabilistic Algorithms and
                                  Straight-Line Programs for Some Rank
                                  Decision Problems  . . . . . . . . . . . 227--232
                  J.-J. Pansiot   A note on Post's correspondence problem  233--233
                Bing Chao Huang   An algorithm for inverting a permutation 237--238
                Jozef Winkowski   Protocols of Accessing Overlapping Sets
                                  of Resources . . . . . . . . . . . . . . 239--243
                 Max Crochemore   An optimal algorithm for computing the
                                  repetitions in a word  . . . . . . . . . 244--250
                    M. Y. Vardi   The decision problem for database
                                  dependencies . . . . . . . . . . . . . . 251--254
              Jürgen Ebert   A sensitive transitive closure algorithm 255--258


Information Processing Letters
Volume 13, Number 1, October ??, 1981

                 Osamu Watanabe   A fast algorithm for finding all
                                  shortest paths . . . . . . . . . . . . . 1--3
           Gilbert N. Lewis and   
           Nancy J. Boynton and   
               F. Warren Burton   Expected Complexity of Fast Search with
                                  Uniformly Distributed Data . . . . . . . 4--7
                James A. Storer   Constructing Full Spanning Trees for
                                  Cubic Graphs . . . . . . . . . . . . . . 8--11
            Oscar H. Ibarra and   
                   Shlomo Moran   Deterministic and probabilistic
                                  algorithms for maximum bipartite
                                  matching via fast matrix multiplication  12--15
                 James F. Korsh   Greedy Binary Search Trees are Nearly
                                  Optimal  . . . . . . . . . . . . . . . . 16--19
             A. K. Agrawala and   
                 S. K. Tripathi   On the optimality of semidynamic routing
                                  schemes  . . . . . . . . . . . . . . . . 20--22
           K. Ramamohanarao and   
                 R. Sacks-Davis   Hardware Address Translation for
                                  Machines with a Large Virtual Memory . . 23--29
                 G. Senizergues   A new class of C.F.L. for which the
                                  equivalence is decidable . . . . . . . . 30--34
          Hamish I. E. Gunn and   
               David M. Harland   Degrees of Constancy in Programming
                                  Languages  . . . . . . . . . . . . . . . 35--38
              Yu. G. Stoyan and   
                S. V. Smelyakov   An approach to the problems of routing
                                  optimization in the regions of intricate
                                  shape  . . . . . . . . . . . . . . . . . 39--43

Information Processing Letters
Volume 13, Number 2, November 13, 1981

          Mireille Clerbout and   
                 Michel Latteux   The inclusion of D0L in MULTI-RESET  . . 45--47
                  O. M. Makarov   Using duality for the synthesis of an
                                  optimal algorithm involving matrix
                                  multiplication . . . . . . . . . . . . . 48--49
                    R. Hood and   
                    R. Melville   Real-time queue operations in Pure LISP  50--54
         Mikhail J. Atallah and   
                S. Rao Kosaraju   An adversary-based lower bound for
                                  sorting  . . . . . . . . . . . . . . . . 55--57
                Wojciech Rytter   The dynamic simulation of recursive and
                                  stack manipulating programs  . . . . . . 58--63
               Mireille Regnier   On the Average Height of Trees in
                                  Digital Search and Dynamic Hashing . . . 64--66
           Ysmar V. Silva Filho   Optimal Choice of Discriminators in a
                                  Balanced $k$-$d$ Binary Search Tree  . . 67--70
                     V. Ya. Pan   The lower bounds on the additive
                                  complexity of bilinear problems in terms
                                  of some algebraic quantities . . . . . . 71--72
                 Ronald V. Book   NTS grammars and Church--Rosser systems  73--76
                   J. S. Vitter   A Shared-Memory Scheme for Coalesced
                                  Hashing  . . . . . . . . . . . . . . . . 77--79
                 Akira Nakamura   Some Remarks on One-Pebble Rectangular
                                  Array Acceptors  . . . . . . . . . . . . 80--84
                   Shlomo Moran   A note on: ``Shortest-path problem is
                                  not harder than matrix multiplication''
                                  [Inform. Process. Lett. \bf 11 (1980),
                                  no. 3, 134--136; MR 81k:68036] by F.
                                  Romani. With a reply by Romani . . . . . 85--86

Information Processing Letters
Volume 13, Number 3, December 13, 1981

            Oscar H. Ibarra and   
                Louis E. Rosier   On the Decidability of Equivalence for
                                  Deterministic Pushdown Transducers . . . 89--93
                Hideki Yamasaki   On Weak Persistency of Petri Nets  . . . 94--97
                  Tat Hung Chan   Deciding Freeness for Program Schemes
                                  with a Single Unary Function . . . . . . 98--102
               R. H. Barlow and   
                D. J. Evans and   
                  J. Shanehichi   A parallel merging algorithm . . . . . . 103--106
                  Refael Hassin   Maximum flow in $(s,\,t)$ planar
                                  networks . . . . . . . . . . . . . . . . 107--107
             A. Ehrenfeucht and   
                   G. Rozenberg   On the subword complexity of D0L
                                  languages with a constant distribution   108--113
                     R. S. Bird   The jogger's problem . . . . . . . . . . 114--117
                 M. D. Atkinson   The cyclic Towers of Hanoi . . . . . . . 118--119
      Donald MacDavid Tolle and   
             William E. Siddall   On the Complexity of Vector Computations
                                  in Binary Tree Machines  . . . . . . . . 120--124
              D. E. Denning and   
                  H. Meijer and   
                F. B. Schneider   More on master keys for group sharing    125--126
     J. L. A. Van De Snepscheut   Synchronous Communication Between
                                  Asynchronous Components  . . . . . . . . 127--130

Information Processing Letters
Volume 13, Number 4--5, End ??, 1981

  Christos H. Papadimitriou and   
             Mihalis Yannakakis   The clique problem for planar graphs . . 131--133
                       G. Barth   An Alternative for the Implementation of
                                  the Knuth-Morris-Pratt Algorithm . . . . 134--137
                R. H. Davis and   
                 C. Rinaldi and   
               C. J. Trebilcock   Data Compression in Limited Capacity
                                  Microcomputer Systems  . . . . . . . . . 138--141
                Wojciech Rytter   Time complexity of languages recognized
                                  by one-way multihead pushdown automata   142--144
                Wojciech Rytter   A hardest language recognized by two-way
                                  nondeterministic pushdown automata . . . 145--146
  V. K. Sabel\cprimefel\cprimed   Tree equivalence of linear recursive
                                  schemata is polynomial-time decidable    147--153
               Alan A. Bertossi   The edge Hamiltonian path problem is
                                  NP-complete  . . . . . . . . . . . . . . 157--159
             L. Siklóssy   Efficient query evaluation in relational
                                  data bases with missing values . . . . . 160--163
                    M. Blum and   
                 R. M. Karp and   
              O. Vornberger and   
        C. H. Papadimitriou and   
                  M. Yannakakis   The complexity of testing whether a
                                  graph is a superconcentrator . . . . . . 164--167
              Jacob T. Schwartz   Finding the minimum distance between two
                                  convex polygons  . . . . . . . . . . . . 168--170
                  M. Ancona and   
                    V. Gianuzzi   A new method for implementing ${\rm
                                  LR}(k)$ tables . . . . . . . . . . . . . 171--176
            H. Edelsbrunner and   
                   H. A. Maurer   On the intersection of orthogonal
                                  objects  . . . . . . . . . . . . . . . . 177--181
             Akira Nakamura and   
                   Kunio Aizawa   Acceptors for isometric parallel
                                  context-free array languages . . . . . . 182--186
                 M. H. Williams   A systematic test for extended operator
                                  precedence . . . . . . . . . . . . . . . 187--190
                 Hiroto Yasuura   Width and Depth of Combinational Logic
                                  Circuits . . . . . . . . . . . . . . . . 191--194
    R\=usi\lfhookn\vs Freivalds   Projections of languages recognizable by
                                  probabilistic and alternating finite
                                  multitape automata . . . . . . . . . . . 195--198
                R. K. Arora and   
                   N. K. Sharma   Guarded Procedure: a Distributed
                                  Programming Concept  . . . . . . . . . . 199--203
                   G. Guida and   
                   M. Somalvico   Multi-problem-solving: knowledge
                                  representation and system architecture   204--214
                J. M. Troya and   
                     A. Vaquero   An approximation algorithm for reducing
                                  expected head movement in linear storage
                                  devices  . . . . . . . . . . . . . . . . 218--220


Information Processing Letters
Volume 14, Number 1, March 27, 1982

                 Alfred Schmitt   On the computational power of the floor
                                  function . . . . . . . . . . . . . . . . 1--3
                  Ben-Zion Chor   Arithmetic of finite fields  . . . . . . 4--6
                Dhruva Nath and   
               S. N. Maheshwari   Parallel Algorithms for the Connected
                                  Components and Minimal Spanning Tree
                                  Problems . . . . . . . . . . . . . . . . 7--11
         Andries E. Brouwer and   
            Peter van Emde Boas   A note on: ``Master keys for group
                                  sharing'' [Inform. Process. Lett. \bf 12
                                  (1981), no. 1, 23--25; MR 82d:94046] by
                                  D. E. Denning and F. B. Schneider  . . . 12--14
               Ronald Backhouse   Writing a number as the sum of two
                                  squares: a new solution  . . . . . . . . 15--17
                 E. Gelenbe and   
                       D. Gardy   On the size of projections . . . . . . . 18--21
              Hamish I. E. Gunn   Compile Time Type Checking of Structure
                                  Field Accessing  . . . . . . . . . . . . 22--25
                R. Endre Tarjan   A hierarchical clustering algorithm
                                  using strong components  . . . . . . . . 26--29
            Robert Endre Tarjan   Sensitivity analysis of minimum spanning
                                  trees and shortest path trees  . . . . . 30--33
            Jan van Leeuwen and   
                  Maurice Nivat   Efficient recognition of rational
                                  relations  . . . . . . . . . . . . . . . 34--38
                       Ker-I Ko   Some observations on the probabilistic
                                  algorithms and NP-hard problems  . . . . 39--43
                    Shmuel Zaks   Generation and ranking of $K$-ary trees  44--48

Information Processing Letters
Volume 14, Number 2, April 20, 1982

    L. Fariñas Del Cerro   A simple deduction method for modal
                                  logic  . . . . . . . . . . . . . . . . . 49--51
                 A. O. Slisenko   Context-free grammars as a tool for
                                  describing polynomial-time subclasses of
                                  hard problems  . . . . . . . . . . . . . 52--56
               M. H. Graham and   
                A. O. Mendelzon   Strong equivalence of relational
                                  expressions under dependencies . . . . . 57--62
             J. C. Lagarias and   
                D. E. Swartwout   Minimal storage representations for
                                  binary relations . . . . . . . . . . . . 63--66
                Guiseppina Gini   The automatic synthesis of iterative
                                  programs . . . . . . . . . . . . . . . . 67--73
            H. Edelsbrunner and   
               H. A. Maurer and   
              D. G. Kirkpatrick   Polygonal intersection searching . . . . 74--79
             J. A. Bergstra and   
                J.-J. Ch. Meyer   A simple transfer lemma for algebraic
                                  specifications . . . . . . . . . . . . . 80--85
                  Eliezer Upfal   Formal correctness proofs of a
                                  nondeterministic program . . . . . . . . 86--92
               Lud\vek Ku\vcera   Parallel computation and conflicts in
                                  memory access  . . . . . . . . . . . . . 93--96

Information Processing Letters
Volume 14, Number 3, May 16, 1982

           Takashi Yokomori and   
                Derick Wood and   
          Klaus-Jörn Lange   A three-restricted normal form theorem
                                  for ETOL languages . . . . . . . . . . . 97--100
                   Jorma Tarhio   LR Parsing of Some Ambiguous Grammars    101--103
        Dietmar Wätjen and   
              Werner Struckmann   An algorithm for verifying equations of
                                  morphisms in a category  . . . . . . . . 104--108
                 K. N. King and   
           Barbara Smith-Thomas   An optimal algorithm for sink-finding    109--111
               J.-L. Lassez and   
               V. L. Nguyen and   
                E. A. Sonenberg   Fixed point theorems and semantics: a
                                  folk tale  . . . . . . . . . . . . . . . 112--116
               R. H. Barlow and   
                D. J. Evans and   
                   J. Shanehchi   Parallel multisection for the
                                  determination of the eigenvalues of
                                  symmetric quindiagonal matrices  . . . . 117--118
          Johannes Röhrich   A hybrid of Quicksort with $O(n \log n)$
                                  worst case complexity  . . . . . . . . . 119--123
       Herbert Edelsbrunner and   
               Mark H. Overmars   On the equivalence of some rectangle
                                  problems . . . . . . . . . . . . . . . . 124--127
            Calvin C. Elgot and   
             Alan J. Perlis and   
                Lawrence Snyder   A syntax-free semantics for the APL
                                  operators  . . . . . . . . . . . . . . . 128--131
          Dzenan Ridjanovic and   
              Michael L. Brodie   Defining Database Dynamics with
                                  Attribute Grammars . . . . . . . . . . . 132--138
                    J. F. Korsh   Growing nearly optimal binary search
                                  trees  . . . . . . . . . . . . . . . . . 139--143
                     Dario Bini   Reply to the paper: ``The numerical
                                  instability of Bini's algorithm''
                                  [Inform. Process. Lett. \bf 12 (1981),
                                  no. 1, 17--19; MR 82i:65029] by N. K.
                                  Tsao . . . . . . . . . . . . . . . . . . 144--145

Information Processing Letters
Volume 14, Number 4, June 13, 1982

                   M. Jakobsson   Evaluation of a hierarchical bit-vector
                                  compression technique  . . . . . . . . . 147--149
              Jack A. Orenstein   Multidimensional Tries Used for
                                  Associative Searching  . . . . . . . . . 150--157
               Hiroshi Umeo and   
             Kenichi Morita and   
                Kazuhiro Sugata   Deterministic One-Way Simulation of
                                  Two-Way Real-Time Cellular Automata and
                                  its Related Problems . . . . . . . . . . 158--161
                     G. Beretta   Monte Carlo estimation of numerical
                                  stability in fast algorithms for systems
                                  of bilinear forms  . . . . . . . . . . . 162--167
       Paul Franchi-Zannettacci   An extension to trees of the Sardinas
                                  and Patterson algorithm  . . . . . . . . 168--173
                   R. Demolombe   Generalized division for relational
                                  algebraic language . . . . . . . . . . . 174--178
           Ernst-E. E. Doberkat   Asymptotic estimates for the higher
                                  moments of the expected behavior of
                                  straight insertion sort  . . . . . . . . 179--182
         Michael J. Fischer and   
                 Nancy A. Lynch   A lower bound for the time to assure
                                  interactive consistency  . . . . . . . . 183--186
               Jiann H. Jou and   
             Patrick C. Fischer   The complexity of recognizing $3{\rm
                                  NF}$ relation schemes  . . . . . . . . . 187--190
                Jack Minker and   
                      Guy Zanon   An extension to linear resolution with
                                  selection function . . . . . . . . . . . 191--194
              Bengt Aspvall and   
           Michael F. Plass and   
            Robert Endre Tarjan   Erratum: ``A linear-time algorithm for
                                  testing the truth of certain quantified
                                  Boolean formulas'' [Inform. Process.
                                  Lett. \bf 8 (1979), no. 3, 121--123; MR
                                  80b:68050] . . . . . . . . . . . . . . . 195--195

Information Processing Letters
Volume 14, Number 5, July 23, 1982

               Clelia De Felice   On the triangle conjecture . . . . . . . 197--200
               F. Warren Burton   A linear space translation of functional
                                  programs to Turner combinators . . . . . 201--204
               F. Warren Burton   An efficient functional implementation
                                  of FIFO queues . . . . . . . . . . . . . 205--206
                  Anton Nijholt   A note on the sufficiency of
                                  Soko\lowski's criterion for context-free
                                  languages  . . . . . . . . . . . . . . . 207--207
                P. G. Reddy and   
             Subhash Bhalla and   
                   B. E. Prasad   A model of concurrency control in
                                  distributed database systems . . . . . . 208--213
             J. G. Shanthikumar   A recursive algorithm to generate joint
                                  probability distribution of arrivals
                                  from exponential sources during a random
                                  time interval  . . . . . . . . . . . . . 214--217
                Johnson M. Hart   Permutation Inversions and
                                  Multidimensional Cumulative Distribution
                                  Functions  . . . . . . . . . . . . . . . 218--222
           David A. Carlson and   
                 John E. Savage   Extreme time-space tradeoffs for graphs
                                  with small space requirements  . . . . . 223--227
          Reuven Bar-Yehuda and   
                    Uzi Vishkin   Complexity of finding $k$-path-free
                                  dominating sets in graphs  . . . . . . . 228--232
                   Carla Savage   Depth-First Search and the Vertex Cover
                                  Problem  . . . . . . . . . . . . . . . . 233--235
                  Heinz Zemanek   Obituary: Victor Mikha\uìlovich Glushkov
                                  (1923--1982) . . . . . . . . . . . . . . 236--237
               R. E. Krichevsky   Letter to the editor: ``A family of
                                  codes commutatively equivalent to prefix
                                  codes'' [Inform. Process. Lett. \bf 12
                                  (1981), no. 1, 1--4; MR 82j:94021] by S.
                                  Mauceri and A. Restivo . . . . . . . . . 238--238


Information Processing Letters
Volume 15, Number 1, August 19, 1982

                  F. Luccio and   
                       L. Pagli   A linear algorithm to determine minimal
                                  spanning forests in chain graphs . . . . 1--4
                Wojciech Rytter   A note on two-way nondeterministic
                                  pushdown automata  . . . . . . . . . . . 5--9
              J.-C. Bermond and   
                 C. Delorme and   
               J.-J. Quisquater   Tables of large graphs with given degree
                                  and diameter . . . . . . . . . . . . . . 10--13
        Larry J. Stockmeyer and   
              Vijay V. Vazirani   NP-completeness of some generalizations
                                  of the maximum matching problem  . . . . 14--19
                    C. Bron and   
             E. J. Dijkstra and   
                S. D. Swierstra   A memory management unit for the optimal
                                  exploitation of a small address space    20--22
                 C. H. C. Leung   Optimal database reorganisation: some
                                  practical difficulties . . . . . . . . . 23--27
               Maciej M. Sys\lo   A labeling algorithm to recognize a line
                                  digraph and output its root graph  . . . 28--30
        Albert C. Greenberg and   
          Richard E. Ladner and   
        Michael S. Paterson and   
                      Zvi Galil   Efficient Parallel Algorithms for Linear
                                  Recurrence Computation . . . . . . . . . 31--35
               Peter M. Winkler   On computability of the mean deviation   36--38
            Karel Culik, II and   
                    Derick Wood   A note on some tree similarity measures  39--42
                   Leon S. Levy   An improved list-searching algorithm . . 43--45

Information Processing Letters
Volume 15, Number 2, September 6, 1982

                 G. K. Manacher   Steady-paced-output and
                                  fractional-on-line algorithms on a RAM   47--52
              C. M. Eastman and   
                   M. Zemankova   Partially Specified Nearest Neighbor
                                  Searches Using $k$-$d$ Trees . . . . . . 53--56
      Jean Pierre Jouannaud and   
                Pierre Lescanne   On Multiset Orderings  . . . . . . . . . 57--63
                    T. R. Walsh   The Towers of Hanoi revisited: moving
                                  the rings by counting the moves  . . . . 64--67
                Michael G. Main   Permutations are not context-free: an
                                  application of the Interchange Lemma . . 68--71
             Allen Goldberg and   
                Paul Purdom and   
                  Cynthia Brown   Average Time Analyses of Simplified
                                  Davis--Putnam Procedures . . . . . . . . 72--75
              Leon \Lukaszewicz   Universal Grammars . . . . . . . . . . . 76--80
                   Ingo Wegener   Best possible asymptotic bounds on the
                                  depth of monotone functions in
                                  multivalued logic  . . . . . . . . . . . 81--83
             J. L. Balcazar and   
                        J. Diaz   A note on a theorem by Ladner  . . . . . 84--86
                    Amir Schoor   Fast Algorithm for Sparse Matrix
                                  Multiplication . . . . . . . . . . . . . 87--89

Information Processing Letters
Volume 15, Number 3, October 11, 1982

               Michael Spyratos   A homomorphism theorem for data base
                                  mappings . . . . . . . . . . . . . . . . 91--96
                  Anton Nijholt   On the relationship between the ${\rm
                                  LL}(k)$ and ${\rm LR}(k)$ grammars . . . 97--101
                Wojciech Rytter   Time complexity of unambiguous path
                                  systems  . . . . . . . . . . . . . . . . 102--104
                P. G. Reddy and   
                  S. Bhalla and   
                   B. E. Prasad   Robust, centralized certifier based
                                  concurrency control for distributed
                                  databases  . . . . . . . . . . . . . . . 105--110
      Waldemar Korczy\'nski and   
         Józef Winkowski   A communication concept for distributed
                                  systems  . . . . . . . . . . . . . . . . 111--114
                  To-Yat Cheung   A statistical model for estimating the
                                  number of records in a relational
                                  database . . . . . . . . . . . . . . . . 115--118
        Teofilo F. Gonzalez and   
              Donald B. Johnson   Sorting numbers in linear expected time
                                  and optimal extra space  . . . . . . . . 119--124
                   Hiroshi Imai   Finding connected components of an
                                  intersection graph of squares in the
                                  Euclidean plane  . . . . . . . . . . . . 125--128
         Edsger W. Dijkstra and   
          A. J. M. van Gasteren   An Introduction to Three Algorithms for
                                  Sorting in Situ  . . . . . . . . . . . . 129--134
                  M. Becker and   
              W. Degenhardt and   
               J. Doenhardt and   
                  S. Hertel and   
                 G. Kaninke and   
                   W. Keber and   
                K. Mehlhorn and   
              S. Näher and   
                 H. Rohnert and   
                      T. Winter   A probabilistic algorithm for vertex
                                  connectivity of graphs . . . . . . . . . 135--136

Information Processing Letters
Volume 15, Number 4, October 31, 1982

                   F. L. Morris   Another compacting garbage collector . . 139--142
             J. A. Bergstra and   
                   J. V. Tucker   Two Theorems About the Completeness of
                                  Hoare's Logic  . . . . . . . . . . . . . 143--149
         Jan Ma\luszy\'nski and   
    Jörgen Fischer Nilsson   Grammatical Unification  . . . . . . . . 150--158
      A. W\lodzimierz Mostowski   Determinancy of sinking automata on
                                  infinite trees and inequalities between
                                  various Rabin's pair indices . . . . . . 159--163
             Katsushi Inoue and   
             Itsuo Takanami and   
              Hiroshi Taniguchi   A note on alternating on-line Turing
                                  machines . . . . . . . . . . . . . . . . 164--168
               Mamoru Hoshi and   
                Toshitsugu Yuba   A counter example to a monotonicity
                                  property of $k$-$d$ trees  . . . . . . . 169--173
                    S. Ceri and   
                   G. Pelagatti   A solution method for the non-additive
                                  resource allocation problem in
                                  distributed system design  . . . . . . . 174--178
                     L. Goh and   
                       D. Rotem   Recognition of Perfect Elimination
                                  Bipartite Graphs . . . . . . . . . . . . 179--182
                   Micha Sharir   Fast Composition of Sparse Maps  . . . . 183--185
                Peter J. Slater   A linear algorithm for the number of
                                  degree constrained subforests of a tree  186--188

Information Processing Letters
Volume 15, Number 5, December 10, 1982

         Timo Leipälä   On Optimal Multilevel Indexed Sequential
                                  Files  . . . . . . . . . . . . . . . . . 191--195
                  P. T. Highnam   The ears of a polygon  . . . . . . . . . 196--198
           Andrzej Szepietowski   A finite $5$-pebble-automaton can search
                                  every maze . . . . . . . . . . . . . . . 199--204
                 Lutz M. Wegner   Sorting a linked list with equal keys    205--208
           George S. Lueker and   
                 Dan E. Willard   A data structure for dynamic range
                                  queries  . . . . . . . . . . . . . . . . 209--213
                 Tatsuya Motoki   A note on upper bounds for the selection
                                  problem  . . . . . . . . . . . . . . . . 214--219
             Harry R. Lewis and   
                Richard Statman   Unifiability is complete for
                                  co-NLogSpace . . . . . . . . . . . . . . 220--222
          Patrick Shen-pei Wang   A new hierarchy of two-dimensional array
                                  languages  . . . . . . . . . . . . . . . 223--226
                Markku Tamminen   Extendible Hashing with Overflow . . . . 227--232
               Quentin F. Stout   Drawing Straight Lines with a Pyramid
                                  Cellular Automaton . . . . . . . . . . . 233--237
           Arthur M. Farley and   
           Andrzej Proskurowski   Directed Maximal-Cut Problems  . . . . . 238--241


Information Processing Letters
Volume 16, Number 1, January 24, 1983

  Friedhelm Meyer Auf Der Heide   Infinite Cube-Connected Cycles . . . . . 1--2
           Alan A. Bertossi and   
         Maurizio A. Bonuccelli   Preemptive Scheduling of Periodic Jobs
                                  in Uniform Multiprocessor Systems  . . . 3--6
             A. Ehrenfeucht and   
                   G. Rozenberg   On the Subword Complexity of Locally
                                  Catenative DOL Languages . . . . . . . . 7--9
               Vitit Kantabutra   Traveling salesman cycles are not always
                                  subgraphs of Vorono\uì duals  . . . . . . 11--12
               Ronald Fagin and   
                 Moshe Y. Vardi   Armstrong Databases for Functional and
                                  Inclusion Dependencies . . . . . . . . . 13--19
                       A. Perko   A representation of disjoint sets with
                                  fast initialization  . . . . . . . . . . 21--21
            Kenneth L. Clarkson   A modification of the greedy algorithm
                                  for vertex cover . . . . . . . . . . . . 23--25
                 Michel Latteux   On a language without star . . . . . . . 27--30
           Yves Métivier   About the rewriting systems produced by
                                  the Knuth Bendix completion algorithm    31--34
       Ralf Hartmut Güting   Stabbing $C$-Oriented Polygons . . . . . 35--40
                   Ingo Wegener   Relating monotone formula size and
                                  monotone depth of Boolean functions  . . 41--42
             Lewis Neale Lester   Accuracy of Approximating Queueing
                                  Network Departure Processes with
                                  Independent Renewal Processes  . . . . . 43--48

Information Processing Letters
Volume 16, Number 2, February 26, 1983

      Joanna J\polhkedrzejowicz   On the enlargement of the class of
                                  regular languages by the shuffle closure 51--54
                Juris Hartmanis   On sparse sets in ${\rm NP}-{\rm P}$ . . 55--60
                  Lloyd Allison   Stable Marriages by Coroutines . . . . . 61--65
          Christopher W. Fraser   A generalization of two code ordering
                                  optimizations  . . . . . . . . . . . . . 67--70
                    S. Eichholz   Optimal networks for distributing
                                  nonsequential programs . . . . . . . . . 71--74
               Bernard Chazelle   A decision procedure for optimal
                                  polyhedron partitioning  . . . . . . . . 75--78
                  B. Alpern and   
                F. B. Schneider   Key exchange using keyless cryptography  79--81
                    Micha Hofri   Should the Two-Headed Disk Be Greedy?
                                  --- Yes, It Should . . . . . . . . . . . 83--85
                   Dan Gusfield   Connectivity and edge-disjoint spanning
                                  trees  . . . . . . . . . . . . . . . . . 87--89
                    T. R. Walsh   Iteration strikes back---at the cyclic
                                  Towers of Hanoi  . . . . . . . . . . . . 91--93
                 T. Ibaraki and   
                       N. Katoh   On-line computation of transitive
                                  closures of graphs . . . . . . . . . . . 95--97
        Christopher R. Wood and   
       Eduardo B. Fernandez and   
                     Tomas Lang   Minimization of Demand Paging for the
                                  LRU Stack Model of Program Behavior  . . 99--104

Information Processing Letters
Volume 16, Number 3, April 15, 1983

            Robert L. Constable   Programs as proofs: a synopsis . . . . . 105--112
              Robert J. McGlinn   Is SSS$^*$ better than alpha-beta  . . . 113--120
        Eljas Soisalon-Soininen   On computing approximate convex hulls    121--126
                Wojciech Rytter   Time Complexity of Loop-Free Two-Way
                                  Pushdown Automata  . . . . . . . . . . . 127--129
                Markku Tamminen   Analysis of $N$-trees  . . . . . . . . . 131--137
            Toshitsugu Yuba and   
        Yoshinori Yamaguchi and   
                 Toshio Shimada   A control mechanism of a Lisp-based
                                  data-driven machine  . . . . . . . . . . 139--143
             Rakesh Agrawal and   
                David J. Dewitt   Updating Hypothetical Data Bases . . . . 145--146
                  I. K. Rystsov   Polynomial complete problems in automata
                                  theory . . . . . . . . . . . . . . . . . 147--151
              Marco A. Casanova   The theory of functional and subset
                                  dependencies over relational expressions 153--160

Information Processing Letters
Volume 16, Number 4, May 13, 1983

           J. L. Deléage   An application of a transfer lemma . . . 161--163
                  Stefan Hertel   Smoothsort's Behavior on Presorted
                                  Sequences  . . . . . . . . . . . . . . . 165--170
           Greg N. Frederickson   Scheduling Unit-Time Tasks with Integer
                                  Release Times and Deadlines  . . . . . . 171--173
                 Errol L. Lloyd   On a Simple Deadlock Recovery Problem    175--178
             Max Crochemore and   
             Michel Le Rest and   
                Philippe Wender   An optimal test on finite unavoidable
                                  sets of words  . . . . . . . . . . . . . 179--180
                    Chee K. Yap   A hybrid algorithm for the shortest path
                                  between two nodes in the presence of few
                                  negative arcs  . . . . . . . . . . . . . 181--182
                Takao Tsuda and   
               Takashi Sato and   
                Takaaki Tatsumi   Generalization of Floyd's model on
                                  permuting information in idealized
                                  two-level storage  . . . . . . . . . . . 183--188
               Masanori Fushimi   Increasing the orders of
                                  equidistribution of the leading bits of
                                  the Tausworthe sequence  . . . . . . . . 189--192
               Bernard Chazelle   An improved algorithm for the
                                  fixed-radius neighbor problem  . . . . . 193--198
                Wojciech Rytter   A simulation result for two-way pushdown
                                  automata . . . . . . . . . . . . . . . . 199--202
                   A. Bossi and   
                   N. Cocco and   
                     L. Colussi   A divide-and-conquer approach to general
                                  context-free parsing . . . . . . . . . . 203--208
              Uwe Schöning   On the structure of $\Delta^p_2$ . . . . 209--211
             Allen Goldberg and   
                Paul Purdom and   
                  Cynthia Brown   Corrigendum: ``Average time analyses of
                                  simplified Davis--Putnam procedures''
                                  [Inform. Process. Lett. \bf 15 (1982),
                                  no. 2, 72--75] . . . . . . . . . . . . . 213--213

Information Processing Letters
Volume 16, Number 5, June 10, 1983

         Edsger W. Dijkstra and   
            W. H. J. Feijen and   
          A. J. M. van Gasteren   Derivation of a Termination Detection
                                  Algorithm for Distributed Computations   217--219
                   Andrzej Duda   The effects of checkpointing on program
                                  execution time . . . . . . . . . . . . . 221--229
                   Arturo Carpi   On the size of a square-free morphism on
                                  a three letter alphabet  . . . . . . . . 231--235
                     F. Murtagh   Expected-time complexity results for
                                  hierarchic clustering algorithms which
                                  use cluster centres  . . . . . . . . . . 237--241
                       K. Ozawa   Considerations on the similarity
                                  measures between index terms . . . . . . 243--246
                  Jacques Cohen   A note on a fast algorithm for sparse
                                  matrix multiplication  . . . . . . . . . 247--248
              John Zahorjan and   
            Barbara J. Bell and   
              Kenneth C. Sevcik   Estimating Block Transfers When Record
                                  Access Probabilities are Non-Uniform . . 249--252
            Robert Endre Tarjan   Updating a Balanced Search Tree in
                                  $O(1)$ Rotations . . . . . . . . . . . . 253--257
              H. P. Kriegel and   
                    Y. S. Kwong   Insertion-Safeness in Balanced Trees . . 259--264
                  Rudolf Freund   Init and Anf operating on
                                  $\omega$-languages . . . . . . . . . . . 265--269


Information Processing Letters
Volume 17, Number 1, July 19, 1983

                       M. C. Er   Computing Sums of Order-$k$ Fibonacci
                                  Numbers in Log Time  . . . . . . . . . . 1--5
                Michael Willett   Trapdoor Knapsacks without
                                  Superincreasing Structure  . . . . . . . 7--11
                F. Cesarini and   
                        G. Soda   An algorithm to construct a compact
                                  $B$-tree in case of ordered keys . . . . 13--16
             Ronald C. Richards   Shape Distribution of Height-Balanced
                                  Trees  . . . . . . . . . . . . . . . . . 17--20
                 Henry R. Tirri   Simulation, Reduction and Preservation
                                  of Correctness Properties of Parallel
                                  Systems  . . . . . . . . . . . . . . . . 21--27
                   Manfred Broy   Denotational Semantics of Communicating
                                  Processes Based on a Language for
                                  Applicative Multiprogramming . . . . . . 29--35
               Robert E. Tarjan   An improved algorithm for hierarchical
                                  clustering using strong components . . . 37--41
                     S. P. Rana   A distributed solution of the
                                  distributed termination problem  . . . . 43--46
                 M. H. Williams   Is an Exit Statement Sufficient? . . . . 47--51
         Cornelius Croitoru and   
                 Emilian Suditu   Perfect Stables in Graphs  . . . . . . . 53--56

Information Processing Letters
Volume 17, Number 2, August 24, 1983

              Jerzy R. Nawrocki   Contiguous Segmentation with Limited
                                  Compacting . . . . . . . . . . . . . . . 57--62
            Michael J. Magazine   Optimality of Intuitive Checkpointing
                                  Policies . . . . . . . . . . . . . . . . 63--66
                  Man-Tak Shing   Optimum Ordered Bi-Weighted Binary Trees 67--70
                 Jozef Vysko\vc   A note on the power of integer division  71--72
                    Po Tong and   
                   E. L. Lawler   A faster algorithm for finding
                                  edge-disjoint branchings . . . . . . . . 73--76
                     Adi Shamir   Embedding Cryptographic Trapdoors in
                                  Arbitrary Knapsack Systems . . . . . . . 77--79
                 Dan E. Willard   Log-Logarithmic Worst-Case Range Queries
                                  are Possible in Space $\Theta (N)$ . . . 81--84
                Youichi Kobuchi   Stability of desynchronized 0L systems   85--90
                Paul De Bra and   
                  Jan Paredaens   An Algorithm for Horizontal
                                  Decompositions . . . . . . . . . . . . . 91--95
               Alan A. Bertossi   Finding Hamiltonian Circuits in Proper
                                  Interval Graphs  . . . . . . . . . . . . 97--101
                    Amir Schorr   Physical Parallel Devices are not Much
                                  Faster Than Sequential Ones  . . . . . . 103--106
               Lud\vek Ku\vcera   Erratum and addendum to: ``Parallel
                                  computation and conflicts in memory
                                  access'' [Inform. Process. Lett. \bf 14
                                  (1982), no. 2, 93--96; MR 83g:68038] . . 107--107

Information Processing Letters
Volume 17, Number 3, October 5, 1983

                   J. J. Martin   Precise typing and filters . . . . . . . 109--112
            Luis Fariñas   Space as time  . . . . . . . . . . . . . 113--115
         Vladimir Lifschitz and   
              Leon Pesotchinsky   A note on the complexity of a partition
                                  algorithm  . . . . . . . . . . . . . . . 117--120
             A. Ehrenfeucht and   
                   G. Rozenberg   On the Subword Complexity of $m$-Free
                                  D0L Languages  . . . . . . . . . . . . . 121--124
                     Sven Skyum   A measure in which Boolean negation is
                                  exponentially powerful . . . . . . . . . 125--128
                    Mark Weiser   Reconstructing Sequential Behavior from
                                  Parallel Behavior Projections  . . . . . 129--135
           Takashi Yokomori and   
               Aravind K. Joshi   Semi-Linearity, Parikh-Boundedness and
                                  Tree Adjunct Languages . . . . . . . . . 137--143
            Gadiel Seroussi and   
                         Fai Ma   On the Arithmetic Complexity of Matrix
                                  Kronecker Powers . . . . . . . . . . . . 145--148
                C. Choffrut and   
                   K. Culik, II   Folding of the Plane and the Design of
                                  Systolic Arrays  . . . . . . . . . . . . 149--153
                       Ali Mili   Verifying Programs by Induction on Their
                                  Data Structure: General Format and
                                  Applications . . . . . . . . . . . . . . 155--160
                 Piotr Wyrostek   On the ``correct prefix property'' in
                                  precedence parsers . . . . . . . . . . . 161--165
                  Zhi Jie Zheng   The duodirun merging algorithm: a new
                                  fast algorithm for parallel merging  . . 167--168
                 M. H. Williams   The problem of absolute privacy  . . . . 169--171

Information Processing Letters
Volume 17, Number 4, November 8, 1983

                 W. F. Clocksin   Real-Time Functional Queue Operations
                                  Using the Logical Variable . . . . . . . 173--175
     John J. Bartholdi, III and   
              Loren K. Platzman   A fast heuristic based on space filling
                                  curves for minimum-weight matching in
                                  the plane  . . . . . . . . . . . . . . . 177--180
             Erkki Mäkinen   Boundedness Testing for Unambiguous
                                  Context-Free Grammars  . . . . . . . . . 181--183
                   Oded Shmueli   Dynamic Cycle Detection  . . . . . . . . 185--188
                  S. Ramesh and   
              S. L. Mehndiratta   The liveness property of on-the-fly
                                  garbage collector---a proof  . . . . . . 189--195
           Anil R. Gangolli and   
             Steven L. Tanimoto   Two Pyramid Machine Algorithms for Edge
                                  Detection in Noisy Binary Images . . . . 197--202
                   Norbert Blum   A note on the ``parallel computation
                                  thesis'' . . . . . . . . . . . . . . . . 203--205
             Mikhail J. Atallah   A linear time algorithm for the
                                  Hausdorff distance between convex
                                  polygons . . . . . . . . . . . . . . . . 207--209
                 Brian H. Mayoh   Models of Programs and Processes . . . . 211--214
              Clemens Lautemann   BPP and the polynomial hierarchy . . . . 215--217
              Leo J. Guibas and   
                   Jorge Stolfi   On computing all north-east nearest
                                  neighbors in the $L_1$ metric  . . . . . 219--223
                   Teruo Hikita   Listing and Counting Subtrees of Equal
                                  Size of a Binary Tree  . . . . . . . . . 225--229

Information Processing Letters
Volume 17, Number 5, December 15, 1983

                     J. S. Rohl   A faster lexicographical $N$ queens
                                  algorithm  . . . . . . . . . . . . . . . 231--233
                 Yao Tin Yu and   
               Mohamed G. Gouda   Unboundedness Detection for a Class of
                                  Communicating Finite-State Machines  . . 235--240
                Eugene W. Myers   An applicative random-access stack . . . 241--248
         Michael J. Fischer and   
            Michael S. Paterson   Storage Requirements for Fair Scheduling 249--250
          Seiichi Nishihara and   
                   Katsuo Ikeda   Address Calculation Algorithms for
                                  Ordered Sets of Combinations . . . . . . 251--253
                  D. T. Barnard   Recursive descent parsing using
                                  implementation languages requiring
                                  definition before use  . . . . . . . . . 255--258
                         T. Ida   Some FP algebra with Currying operation  259--261
                   Reiner Kolla   Where-Oblivious is not Sufficient  . . . 263--268
               Yung H. Tsin and   
                Francis Y. Chin   A general program scheme for finding
                                  bridges  . . . . . . . . . . . . . . . . 269--272
                  Hitohisa Asai   A consideration of a practical
                                  implementation for a new convergence
                                  division . . . . . . . . . . . . . . . . 273--281


Information Processing Letters
Volume 18, Number 1, January 20, 1984

          V. N. Kas\cprimeyanov   Loop Cleaning  . . . . . . . . . . . . . 1--6
                     Jan Magott   Performance Evaluation of Concurrent
                                  Systems Using Petri Nets . . . . . . . . 7--13
                      A. Saoudi   Infinitary Tree Languages Recognized by
                                  $\omega$-automata  . . . . . . . . . . . 15--19
    Hans-Jörg Kreowski and   
             Grzegorz Rozenberg   Note on node-rewriting graph grammars    21--24
                   Neil C. Rowe   Diophantine Inference on a Statistical
                                  Database . . . . . . . . . . . . . . . . 25--31
                Rodney W. Topor   Termination Detection for Distributed
                                  Computations . . . . . . . . . . . . . . 33--36
             Mikhail J. Atallah   Parallel Strong Orientation of an
                                  Undirected Graph . . . . . . . . . . . . 37--39
               Francis Chin and   
                    Cao An Wang   Minimum vertex distance between
                                  separable convex polygons  . . . . . . . 41--45
                  Xiao Long Jin   Large Processors are Good in VLSI Chips  47--49
                  Eiji Yodogawa   A note on array grammars . . . . . . . . 51--54
                       R. Geist   Perception-based configuration design of
                                  computer systems . . . . . . . . . . . . 55--57

Information Processing Letters
Volume 18, Number 2, February 28, 1984

                 M. E. Dyer and   
                   A. M. Frieze   A partitioning algorithm for minimum
                                  weighted Euclidean matching  . . . . . . 59--62
           M. Elizabeth C. Hull   A parallel view of stable marriages  . . 63--66
              Jan Schlörer   Insecurity of Set Controls for
                                  Statistical Databases  . . . . . . . . . 67--71
             Russell Turpin and   
                  Brian A. Coan   Extending Binary Byzantine Agreement to
                                  Multivalued Byzantine Agreement  . . . . 73--76
             Leszek Holenderski   A note on specifying and verifying
                                  concurrent processes . . . . . . . . . . 77--85
               Hirofumi Katsuno   When Do Non-Conflict-Free Multivalued
                                  Dependency Sets Appear?  . . . . . . . . 87--92
          Heung-Soon S. Ihm and   
               Simeon C. Ntafos   On Legal Path Problems in Digraphs . . . 93--98
                F. Scarioni and   
                 H. G. Speranza   A probabilistic analysis of an
                                  error-correcting algorithm for the
                                  Towers of Hanoi puzzle . . . . . . . . . 99--103
                  Satoru Miyano   Remarks on Two-Way Automata with
                                  Weak-Counters  . . . . . . . . . . . . . 105--107
                  C. C. Lee and   
                      D. T. Lee   On a Circle-Cover Minimization Problem   109--115

Information Processing Letters
Volume 18, Number 3, March 30, 1984

                Herbert S. Wilf   Backtrack: an $O(1)$ expected time
                                  algorithm for the graph coloring problem 119--121
                    Eitan Zemel   An $O(n)$ algorithm for the linear
                                  multiple choice Knapsack problem and
                                  related problems . . . . . . . . . . . . 123--128
       Peter Moller-Nielsen and   
              Jorgen Staunstrup   Experiments with a Fast String Searching
                                  Algorithm  . . . . . . . . . . . . . . . 129--135
                  J. H. Remmers   A technique for developing loop
                                  invariants . . . . . . . . . . . . . . . 137--139
                    G. Alia and   
                   F. Barsi and   
                  E. Martinelli   A fast VLSI conversion between binary
                                  and residue systems  . . . . . . . . . . 141--145
            Stuart J. Berkowitz   On Computing the Determinant in Small
                                  Parallel Time Using a Small Number of
                                  Processors . . . . . . . . . . . . . . . 147--150
       György Turán   The critical complexity of graph
                                  properties . . . . . . . . . . . . . . . 151--153
              A. Apostolico and   
                   R. Giancarlo   Pattern matching machine implementation
                                  of a fast test for unique
                                  decipherability  . . . . . . . . . . . . 155--158
          Gordon V. Cormack and   
              R. Nigel Horspool   Algorithms for Adaptive Huffman Codes    159--165
                  Alfonso Miola   Algebraic approach to $p$-adic
                                  conversion of rational numbers . . . . . 167--171
                Thomas Lickteig   A note on border rank  . . . . . . . . . 173--178

Information Processing Letters
Volume 18, Number 4, May 14, 1984

               Gianna Cioni and   
                Antoni Kreczmar   Programmed Deallocation without Dangling
                                  Reference  . . . . . . . . . . . . . . . 179--187
            Alistair Moffat and   
                  Tadao Takaoka   A priority queue for the all pairs
                                  shortest path problem  . . . . . . . . . 189--193
           D. C. S. Allison and   
                     M. T. Noga   The $L_1$ traveling salesman problem . . 195--199
     Jürgen Tiekenheinrich   A $4n$-lower bound on the monotone
                                  network complexity of a one-output
                                  Boolean function . . . . . . . . . . . . 201--202
             Heikki Mannila and   
                   Esko Ukkonen   A simple linear-time algorithm for in
                                  situ merging . . . . . . . . . . . . . . 203--208
            Susumu Yamasaki and   
              Mikio Yoshida and   
              Shuji Doshita and   
                  Mikito Hirata   A new combination of input and unit
                                  deductions for Horn sentences  . . . . . 209--213
                      Eike Best   Fairness and conspiracies  . . . . . . . 215--220
             Vladimir Lifschitz   On verification of programs with GOTO
                                  statements . . . . . . . . . . . . . . . 221--225
                    T. Ohya and   
                     M. Iri and   
                      K. Murota   A fast Voronoi-diagram algorithm with
                                  quaternary tree bucketing  . . . . . . . 227--231
               Paolo Atzeni and   
              Nicola M. Morfuni   Functional Dependencies in Relations
                                  with Null Values . . . . . . . . . . . . 233--238

Information Processing Letters
Volume 18, Number 5, June 18, 1984

                      B. Monien   Deterministic Two-Way One-Head Pushdown
                                  Automata are Very Powerful . . . . . . . 239--242
           M. P. Flé and   
                   G. Roucairol   Multiserialization of Iterated
                                  Transactions . . . . . . . . . . . . . . 243--247
                  Gerhard Barth   An analytical comparison of two string
                                  searching algorithms . . . . . . . . . . 249--256
                 Moshe Y. Vardi   A note on lossless database
                                  decompositions . . . . . . . . . . . . . 257--260
             Nathan Goodman and   
                      Y. C. Tay   A characterization of multivalued
                                  dependencies equivalent to a join
                                  dependency . . . . . . . . . . . . . . . 261--266
               J. Blazewicz and   
                 J. Weglarz and   
                   M. Drabowski   Scheduling independent $2$-processor
                                  tasks to minimize schedule length  . . . 267--273
             M. B. Trakhtenbrot   Some Equivalent Transformations of
                                  Recursive Programs Based on Their
                                  Schematic Properties . . . . . . . . . . 275--283
                Bruno Courcelle   Some negative results concerning DPDAs   285--289
                 Shinsei Tazawa   On the consecutive retrieval property
                                  for generalized binary queries . . . . . 291--293
              D. K. Friesen and   
                 M. A. Langston   A storage-size selection problem . . . . 295--296
         Stanislav \vZák   Letter to the editor: ``Finitary and
                                  infinitary interpretations of
                                  languages'' [Math. Systems Theory \bf 15
                                  (1981/82), no. 3, 251--265; MR
                                  83h:68119] by H. A. Maurer, A. Salomaa
                                  and D. Wood  . . . . . . . . . . . . . . 297--298


Information Processing Letters
Volume 19, Number 1, July 26, 1984

               Hari Madduri and   
                 Raphael Finkel   Extension of the Banker's Algorithm for
                                  Resource Allocation in a Distributed
                                  Operating System . . . . . . . . . . . . 1--8
              Michio Oyamaguchi   Some Remarks on Subclass Containment
                                  Problems for Several Classes of DPDA's   9--12
               Nam Sung Woo and   
              Carl H. Smith and   
                 Ashok Agrawala   A proof of the determinacy property of
                                  the data flow schema . . . . . . . . . . 13--16
                   J. R. Parker   On Converting Character Strings to
                                  Integers . . . . . . . . . . . . . . . . 17--19
            Ulrich Bechtold and   
             Klaus Küspert   On the Use of Extendible Hashing without
                                  Hashing  . . . . . . . . . . . . . . . . 21--26
              Ulrich Faigle and   
                Rainer Schrader   Minimizing Completion Time for a Class
                                  of Scheduling Problems . . . . . . . . . 27--29
          Walter J. Savitch and   
      Paul M. B. Vitányi   On the Power of Real-Time Two-Way
                                  Multihead Finite Automata with Jumps . . 31--35
               Alan A. Bertossi   Dominating sets for split and bipartite
                                  graphs . . . . . . . . . . . . . . . . . 37--40
         P. A. Subrahmanyam and   
                      J.-H. You   On Embedding Functions in Logic  . . . . 41--46
                   Selim G. Akl   An optimal algorithm for parallel
                                  selection  . . . . . . . . . . . . . . . 47--50
                     Udi Manber   A probabilistic lower bound for checking
                                  disjointness of sets . . . . . . . . . . 51--53
              Paul Spirakis and   
                    Chee K. Yap   Strong NP-hardness of moving many discs  55--59

Information Processing Letters
Volume 19, Number 2, August 31, 1984

                 Helmut Alt and   
              Kurt Mehlhorn and   
                   J. Ian Munro   Partial Match Retrieval in Implicit Data
                                  Structures . . . . . . . . . . . . . . . 61--65
            Alain J. Martin and   
                     Martin Rem   A presentation of the Fibonacci
                                  algorithm  . . . . . . . . . . . . . . . 67--68
              G. P. McKeown and   
            V. J. Rayward-Smith   Communication Problems on MIMD Parallel
                                  Computers  . . . . . . . . . . . . . . . 69--73
            Prashant Palvia and   
             Salvatore T. March   Approximating Block Accesses in Database
                                  Organizations  . . . . . . . . . . . . . 75--79
                   E. Luque and   
                      A. Ripoll   Integer Linear Programming for
                                  Microprograms Register Allocation  . . . 81--85
                     Ewa Klupsz   A linear algorithm of a deadlock
                                  avoidance for nonpreemptible resources   87--94
                   Grazia Lotti   Area-time tradeoff for rectangular
                                  matrix multiplication in VLSI models . . 95--98
             Witold Lipski, Jr.   An $O(n \log n)$ Manhattan path
                                  algorithm  . . . . . . . . . . . . . . . 99--102
                  E. J. Weyuker   The complexity of data flow criteria for
                                  test data selection  . . . . . . . . . . 103--109
                 Piotr Wyrostek   Erratum: ``On the `correct prefix
                                  property' in precedence parsers''
                                  [Inform. Process. Lett. \bf 17 (1983),
                                  no. 3, 161--165, MR 85a:68112] . . . . . 111--111

Information Processing Letters
Volume 19, Number 3, October 19, 1984

                  A. Shamir and   
                  C. P. Schnorr   Cryptanalysis of Certain Variants of
                                  Rabin's Signature Scheme . . . . . . . . 113--115
            Joseph M. Treat and   
                Timothy A. Budd   Extensions to Grid Selector Composition
                                  and Compilation in APL . . . . . . . . . 117--123
                     David Avis   Non-Partitionable Point Sets . . . . . . 125--129
                Peter Eades and   
                  Brendan McKay   An algorithm for generating subsets of
                                  fixed size with a strong minimal change
                                  property . . . . . . . . . . . . . . . . 131--133
               Dale Johnson and   
              Barrett R. Bryant   Formal Syntax Methods for Natural
                                  Language . . . . . . . . . . . . . . . . 135--143
         Tomasz Kowaltowski and   
                  Antonio Palma   Another Solution of the Mutual Exclusion
                                  Problem  . . . . . . . . . . . . . . . . 145--146
                R. G. Gupta and   
            V. S. P. Srivastava   On Synthesis of Scheduling Algorithms    147--150
                 Joachim Biskup   Some Variants of the Take-Grant
                                  Protection Model . . . . . . . . . . . . 151--156
                    D. Maio and   
               M. R. Scalas and   
                     P. Tiberio   On Estimating Access Costs in Relational
                                  Databases  . . . . . . . . . . . . . . . 157--161
                      Eike Best   Erratum: ``Fairness and conspiracies''
                                  [Inform. Process. Lett. \bf 18 (1984),
                                  no. 4, 215--220; MR 85h:68053] . . . . . 162--162

Information Processing Letters
Volume 19, Number 4, November 12, 1984

                Wojciech Rytter   On Linear Context-Free Languages and
                                  One-Way Multihead Automata . . . . . . . 163--166
                 M. Chrobak and   
                  B. S. Chlebus   Probabilistic Turing Machines and
                                  Recursively Enumerable Dedekind Cuts . . 167--171
              Ph. Darondeau and   
                        L. Kott   Towards a Formal Proof System for
                                  $\omega$-Rational Expressions  . . . . . 173--177
                  Marek Chrobak   A note on bounded-reversal multipushdown
                                  machines . . . . . . . . . . . . . . . . 179--180
                     Dick Grune   How to produce all sentences from a
                                  two-level grammar  . . . . . . . . . . . 181--185
                   Arturo Carpi   On the Centers of the Set of Weakly
                                  Square-Free Words on a Two Letter
                                  Alphabet . . . . . . . . . . . . . . . . 187--190
                        J. Kral   On software equations  . . . . . . . . . 191--196
                 Michael Kallay   The complexity of incremental convex
                                  hull algorithms in ${\bf R}^d$ . . . . . 197--197
            Clement H. C. Leung   Approximate storage utilisation of
                                  $B$-trees: a simple derivation and
                                  generalisations  . . . . . . . . . . . . 199--201
                    T. R. Walsh   How Evenly Should One Divide to Conquer
                                  Quickly? . . . . . . . . . . . . . . . . 203--208
          Lawrence W. Dowdy and   
             Derek L. Eager and   
            Karen D. Gordon and   
             Lawrence V. Saxton   Throughput Concavity and Response Time
                                  Convexity  . . . . . . . . . . . . . . . 209--212

Information Processing Letters
Volume 19, Number 5, November 26, 1984

      Juhani Karhumäki and   
                    Derick Wood   Inverse Morphic Equivalence on Languages 213--218
           Greg N. Frederickson   On Linear-Time Algorithms for
                                  Five-Coloring Planar Graphs  . . . . . . 219--224
             Erkki Mäkinen   On Derivation Preservation . . . . . . . 225--228
                    Derick Wood   The contour problem for rectilinear
                                  polygons . . . . . . . . . . . . . . . . 229--236
                   Paul Bourret   How to Estimate the Sizes of Domains . . 237--243
               George Tourlakis   An inductive number-theoretic
                                  characterization of NP . . . . . . . . . 245--247
                 Jozef Vysko\vc   A note on Boolean matrix multiplication  249--251
                Pierre McKenzie   Permutations of Bounded Degree Generate
                                  Groups of Polynomial Diameter  . . . . . 253--254
               Goker Gursel and   
              Peter Scheuermann   Asserting the optimality of serial SJRPs
                                  in processing simple queries in chain
                                  networks . . . . . . . . . . . . . . . . 255--260


Information Processing Letters
Volume 20, Number 1, January 2, 1985

                Christine Duboc   Some Properties of Commutation in Free
                                  Partially Commutative Monoids  . . . . . 1--4
             Ronald V. Book and   
                 Friedrich Otto   Cancellation Rules and Extended Word
                                  Problems . . . . . . . . . . . . . . . . 5--11
                A. Mirzaian and   
                   E. Arjomandi   Selection in $x + y$ and Matrices with
                                  Sorted Rows and Columns  . . . . . . . . 13--17
             Erkki Mäkinen   A note on undercover relation  . . . . . 19--21
                  G. P. McKeown   A special purpose MIMD parallel
                                  processor  . . . . . . . . . . . . . . . 23--27
             S. Upendra Rao and   
                 A. K. Majumdar   An algorithm for local compaction of
                                  horizontal microprograms . . . . . . . . 29--33
              Solomon Passy and   
                  Tinko Tinchev   PDL with data constants  . . . . . . . . 35--41
             Silvio Lemos Meira   A linear applicative solution for the
                                  set union problem  . . . . . . . . . . . 43--45
                 Adam C. Bounas   Direct determination of a ``seed''
                                  binary matrix  . . . . . . . . . . . . . 47--50
                 Sushil Jajodia   On Equivalence of Relational and Network
                                  Database Models  . . . . . . . . . . . . 51--54

Information Processing Letters
Volume 20, Number 2, February 15, 1985

                 G. Bilardi and   
                F. P. Preparata   The VLSI optimality of the AKS sorting
                                  network  . . . . . . . . . . . . . . . . 55--59
              David A. Plaisted   The undecidability of self-embedding for
                                  term rewriting systems . . . . . . . . . 61--64
    Jan L. A. Van de Snepscheut   Evaluating Expressions with a Queue  . . 65--66
                    John McLean   A comment on the `basic security
                                  theorem' of Bell and LaPadula  . . . . . 67--70
                  Kohei Noshita   Translation of Turner combinators in
                                  ${O(n \log n)}$ space  . . . . . . . . . 71--74
                P. Widmayer and   
                     C. K. Wong   An optimal algorithm for the maximum
                                  alignment of terminals . . . . . . . . . 75--82
               Satish R. Thatte   On the Correspondence Between Two
                                  Classes of Reduction Systems . . . . . . 83--85
                David Harel and   
                    David Peleg   More on Looping Vs. Repeating in Dynamic
                                  Logic  . . . . . . . . . . . . . . . . . 87--90
               A. J. Auzins and   
                   E. B. Kinber   On Separation of the Emptiness and
                                  Equivalence Problems for Program Schemes 91--93
               D. Beauquier and   
                      D. Perrin   Codeterministic Automata on Infinite
                                  Words  . . . . . . . . . . . . . . . . . 95--98
                   Esko Ukkonen   Upper bounds on the size of ${\rm
                                  LR}(k)$ parsers  . . . . . . . . . . . . 99--103
                Michael G. Main   An infinite square-free co-CFL . . . . . 105--107
                 Subhash C. Kak   How to Detect Tampering of Data  . . . . 109--110

Information Processing Letters
Volume 20, Number 3, April 8, 1985

                 Ernest C. Njau   Details of Distortions in the Computed
                                  Fourier Transforms of Signals. Part I.
                                  Short Periodic Signals . . . . . . . . . 111--113
              Eduardo D. Sontag   Real Addition and the Polynomial
                                  Hierarchy  . . . . . . . . . . . . . . . 115--120
                   Mee Yee Chan   A note on redundant Disk Modulo
                                  allocation . . . . . . . . . . . . . . . 121--123
                Alain J. Martin   The probe: an addition to communication
                                  primitives . . . . . . . . . . . . . . . 125--130
                    E. Lodi and   
                      F. Luccio   Split Sequence Hash Search . . . . . . . 131--136
               Richard Cole and   
                    Chee K. Yap   A parallel median algorithm  . . . . . . 137--139
             Erkki Mäkinen   An undecidable problem for context-free
                                  grammars . . . . . . . . . . . . . . . . 141--142
                Yung Hyang Tsin   An optimal parallel processor bound in
                                  strong orientation of an undirected
                                  graph  . . . . . . . . . . . . . . . . . 143--146
                Baruch Awerbuch   A new distributed depth-first-search
                                  algorithm  . . . . . . . . . . . . . . . 147--150
            Jeffrey Shallit and   
                     Adi Shamir   Number-Theoretic Functions Which are
                                  Equivalent to Number of Divisors . . . . 151--153
                    Hugo Volger   Some Results on Addition/Subtraction
                                  Chains . . . . . . . . . . . . . . . . . 155--160
               W. M. Beynon and   
               C. S. Iliopoulos   Computing a Basis for a Finite Abelian
                                  $p$-Group  . . . . . . . . . . . . . . . 161--163

Information Processing Letters
Volume 20, Number 4, May 10, 1985

                      Emo Welzl   Constructing the Visibility Graph for
                                  $n$-Line Segments in ${O}(n^2)$ Time . . 167--171
                  Mathai Joseph   On a Problem in Real-Time Computing  . . 173--177
             Nicola Santoro and   
              Jeffrey B. Sidney   Interpolation-Binary Search  . . . . . . 179--181
              K. Rangarajan and   
                  S. Arun-Kumar   Fair Derivations in E0L Systems  . . . . 183--188
                 Carroll Morgan   Global and Logical Time in Distributed
                                  Algorithms . . . . . . . . . . . . . . . 189--194
                  David S. Wise   Representing Matrices as Quadtrees for
                                  Parallel Processors  . . . . . . . . . . 195--199
                   J. Mark Keil   Finding Hamiltonian Circuits in Interval
                                  Graphs . . . . . . . . . . . . . . . . . 201--206
                 W. J. Van Gils   How to Cope with Faulty Processors in a
                                  Completely Connected Network of
                                  Communicating Processors . . . . . . . . 207--213
           Costas S. Iliopoulos   Analysis of Algorithms on Problems in
                                  General Abelian Groups . . . . . . . . . 215--220
                 Amiram Yehudai   A note on chains of deterministic
                                  pushdown transducers . . . . . . . . . . 221--222

Information Processing Letters
Volume 20, Number 5, June 12, 1985

                Maciej Slusarek   A note on the dynamic storage allocation
                                  problem  . . . . . . . . . . . . . . . . 223--227
                   John H. Reif   Depth-First Search is Inherently
                                  Sequential . . . . . . . . . . . . . . . 229--234
                    Uzi Vishkin   On Efficient Parallel Strong Orientation 235--240
                Juris Hartmanis   Independence Results About Context-Free
                                  Languages and Lower Bounds . . . . . . . 241--248
                James R. Bitner   Storing Matrices on Disk for Efficient
                                  Row and Column Retrieval . . . . . . . . 249--254
                    Luc Devroye   A note on the expected time required to
                                  construct the outer layer  . . . . . . . 255--257
      Christos H. Papadimitriou   An algorithm for shortest-path motion in
                                  three dimensions . . . . . . . . . . . . 259--263


Information Processing Letters
Volume 21, Number 1, July 10, 1985

                    Hanan Samet   Bidirectional Coroutines . . . . . . . . 1--6
              Juraj Hromkovi\vc   Alternating Multicounter Machines with
                                  Constant Number of Reversals . . . . . . 7--9
                   M. Negri and   
                   G. Pelagatti   Join During Merge: an Improved Sort
                                  Based Algorithm  . . . . . . . . . . . . 11--16
            Gerald Guralnik and   
             Charles Zemach and   
                   Tony Warnock   An algorithm for uniform random sampling
                                  of points in and on a hypersphere  . . . 17--21
                    Linda Pagli   Self-Adjusting Hash Tables . . . . . . . 23--25
               Deepak Kapur and   
       Mukkai S. Krishnamoorthy   Worst-Case Choice for the Stable
                                  Marriage Problem . . . . . . . . . . . . 27--30
                  Se Man Oh and   
                  J. C. H. Park   A note on removing loops from
                                  table-driven code generators . . . . . . 31--34
              Mordechai M. Yung   A secure and useful `keyless
                                  cryptosystem'  . . . . . . . . . . . . . 35--38
            H. Edelsbrunner and   
                   H. A. Maurer   Finding Extreme Points in Three
                                  Dimensions and Solving the Post-Office
                                  Problem in the Plane . . . . . . . . . . 39--47
                   Ingo Wegener   Optimal search with positive switch cost
                                  is NP-hard . . . . . . . . . . . . . . . 49--52
           Takashi Yokomori and   
                Derick Wood and   
          Klaus-Jörn Lange   Erratum: ``A three-restricted normal
                                  form theorem for ETOL languages''
                                  [Inform. Process. Lett. \bf 14 (1982),
                                  no. 3, 97--100; MR 83g:68115]  . . . . . 53--53

Information Processing Letters
Volume 21, Number 2, August 16, 1985

           Vladimir J. Lumelsky   On Fast Computation of Distance Between
                                  Line Segments  . . . . . . . . . . . . . 55--61
             Thomas Rauchle and   
                      Sam Toueg   Exposure to Deadlock for Communicating
                                  Processes is Hard to Detect  . . . . . . 63--68
                 Anne Kaldewaij   On the Decomposition of Sequences into
                                  Ascending Subsequences . . . . . . . . . 69--69
              Juraj Hromkovi\vc   Linear Lower Bounds on Unbounded Fan-In
                                  Boolean Circuits . . . . . . . . . . . . 71--74
            Ladislav Janiga and   
           Václav Koubek   A note on finding minimum cuts in
                                  directed planar networks by parallel
                                  computations . . . . . . . . . . . . . . 75--78
                 Dario Bini and   
                 Victor Ya. Pan   Fast Parallel Polynomial Division via
                                  Reduction to Triangular Toeplitz Matrix
                                  Inversion and to Polynomial Inversion
                                  Modulo a Power . . . . . . . . . . . . . 79--81
            Dietmar Wätjen   Feedback Automata and Their Languages    83--86
      Paul M. B. Vitányi   Square Time is Optimal for Simulation of
                                  One Pushdown Store or One Queue by an
                                  Oblivious One-Head Tape Unit . . . . . . 87--91
                     Van Nguyen   The incompleteness of Misra and Chandy's
                                  proof systems  . . . . . . . . . . . . . 93--96
            Alain J. Martin and   
                 Jerry R. Burch   Fair mutual exclusion with unfair $P$
                                  and $V$ operations . . . . . . . . . . . 97--100
          Clemens Lautemann and   
  Friedhelm Meyer auf der Heide   Lower Time Bounds for Integer
                                  Programming with Two Variables . . . . . 101--105
                Alain J. Martin   Erratum: ``The probe: an addition to
                                  communication primitives'' . . . . . . . 107--107

Information Processing Letters
Volume 21, Number 3, September 5, 1985

              Clark D. Thompson   VLSI Design with Multiple Active Layers  109--111
          Suresh C. Kothari and   
               K. V. S. Ramarao   General Algorithms for the Address
                                  Calculation of Lexicographically Ordered
                                  Tuples . . . . . . . . . . . . . . . . . 113--116
                  D. T. Lee and   
                    Y. T. Ching   The power of geometric duality revisited 117--122
  Joseph JáJá and   
                    Jean Takche   Improved Lower Bounds for Some Matrix
                                  Multiplication Problems  . . . . . . . . 123--127
                 Ted Herman and   
                 K. Mani Chandy   On Distributed Search  . . . . . . . . . 129--133
                     M. Jantzen   A note on a special one-rule semi-Thue
                                  system . . . . . . . . . . . . . . . . . 135--140
                Timothy A. Budd   Creation and Reflexive Rights in
                                  Grammatical Protection Systems . . . . . 141--145
      Paul M. B. Vitányi   An $n^{1.618}$ lower bound on the time
                                  to simulate one queue or two pushdown
                                  stores by one tape . . . . . . . . . . . 147--152
                   Chae Woo Yoo   An approach to the transportation of
                                  computer software  . . . . . . . . . . . 153--157
               B. Codenotti and   
                  F. Romani and   
                       G. Lotti   VLSI Implementation of Fast Solvers for
                                  Band Linear Systems with Constant
                                  Coefficient Matrix . . . . . . . . . . . 159--163

Information Processing Letters
Volume 21, Number 4, October 7, 1985

       Ralf Hartmut Güting   Fast Dynamic Intersection Searching in a
                                  Set of Isothetic Line Segments . . . . . 165--171
              Jean-Paul Laumond   Enumeration of Articulation Pairs of a
                                  Planar Graph . . . . . . . . . . . . . . 173--179
               Bowen Alpern and   
              Fred B. Schneider   Defining Liveness  . . . . . . . . . . . 181--185
                 M. D. Atkinson   On Zigzag Permutations and Comparisons
                                  of Adjacent Elements . . . . . . . . . . 187--189
                Yves Robert and   
               Maurice Tchuente   A systolic array for the longest common
                                  subsequence problem  . . . . . . . . . . 191--198
                J. L. Keedy and   
                  B. Freisleben   On the Efficient Use of Semaphore
                                  Primitives . . . . . . . . . . . . . . . 199--205
             Ching C. Hsiao and   
                  Nien-Tsu Shen   $k$-Fold Bitonic Sort on a
                                  Mesh-Connected Parallel Computer . . . . 207--212
    A. Marchetti-Spaccamela and   
                      G. Romano   On Different Approximation Criteria for
                                  Subset Product Problems  . . . . . . . . 213--218

Information Processing Letters
Volume 21, Number 5, November 18, 1985

                 Bertrand Meyer   Incremental String Matching  . . . . . . 219--227
                     Jan Magott   Performance Evaluation of Systems of
                                  Cyclic Sequential Processes with Mutual
                                  Exclusion Using Petri Nets . . . . . . . 229--232
                   A. J. Kfoury   The unwind property for programs with
                                  bounded memory . . . . . . . . . . . . . 233--238
       W\lodzimierz Dobosiewicz   A note on natural selection  . . . . . . 239--243
            Pavol \vDuri\vs and   
       Ondrej Sýkora and   
         Imrich V\vr\softto and   
              Clark D. Thompson   Tight Chip Area Lower Bounds for
                                  Discrete Fourier and Walsh-Hadamard
                                  Transformations  . . . . . . . . . . . . 245--247
             Kenneth J. Supowit   Decomposing a Set of Points into Chains,
                                  with Applications to Permutation and
                                  Circle Graphs  . . . . . . . . . . . . . 249--252
                  Ulrich Derigs   An Efficient Dijkstra-Like Labeling
                                  Method for Computing Shortest Odd/Even
                                  Paths  . . . . . . . . . . . . . . . . . 253--258
          Ingrid J. M. Birkhoff   A direct routing algorithm for the
                                  bit-reversal permutation on a
                                  shuffle-exchange network . . . . . . . . 259--268
             Heikki Mannila and   
                  Kurt Mehlhorn   A fast algorithm for renaming a set of
                                  clauses as a Horn set  . . . . . . . . . 269--272


Information Processing Letters
Volume 22, Number 1, January 2, 1986

              Philippe Chatelin   On Transformations of Algorithms to
                                  Multiply $2 \times 2$ Matrices . . . . . 1--5
                   Jean Berstel   Every iterated morphism yields a co-CFL  7--9
                 Victor Ya. Pan   The Trade-Off Between the Additive
                                  Complexity and the Asynchronicity of
                                  Linear and Bilinear Algorithms . . . . . 11--14
           Bernd Baumgarten and   
      Peter Ochsenschläger   On termination and phase changes in the
                                  presence of unreliable communication . . 15--20
            Kenneth L. Clarkson   Linear Programming in ${O}(n \times
                                  3^{d^2})$ time . . . . . . . . . . . . . 21--24
                 Andrzej Lingas   The Greedy and Delauney triangulations
                                  are not bad in the average case  . . . . 25--31
                Louis E. Rosier   A Note on Presburger Arithmetic with
                                  Array Segments, Permutation and Equality 33--35
        Mirko K\vrivánek   Hexagonal unit network---a tool for
                                  proving the NP-completeness results of
                                  geometric problems . . . . . . . . . . . 37--41
    Christiaan T. M. Jacobs and   
            Peter Van Emde Boas   Two Results on Tables  . . . . . . . . . 43--48
               V. Kriau\vciukas   Tree-Like Parse and Polynomial
                                  Subclasses of Search Problems  . . . . . 49--54

Information Processing Letters
Volume 22, Number 2, January 18, 1986

         Ivan Stojmenovi\'c and   
        Eljas Soisalon-Soininen   A Note on Approximate Convex Hulls . . . 55--56
               Amos Israeli and   
                    Y. Shiloach   An Improved Parallel Algorithm for
                                  Maximal Matching . . . . . . . . . . . . 57--60
                   Ke-Chang Dai   EDISON-80, a language for modular
                                  programming of parallel processes  . . . 61--72
          M. D. Grigoriadis and   
                   B. Kalantari   A Lower Bound to the Complexity of
                                  Euclidean and Rectilinear Matching
                                  Algorithms . . . . . . . . . . . . . . . 73--76
               Amos Israeli and   
                        A. Itai   A fast and simple randomized parallel
                                  algorithm for maximal matching . . . . . 77--80
              Charles U. Martel   Lower bounds on parallel algorithms for
                                  finding the first maximal independent
                                  set  . . . . . . . . . . . . . . . . . . 81--85
                  Marta Cialdea   Some remarks on the possibility of
                                  extending resolution proof procedures to
                                  intuitionistic logic . . . . . . . . . . 87--90
    Pavel Goral\vcík and   
           Václav Koubek   Verifying nonrigidity  . . . . . . . . . 91--95
                      Marc Snir   Exact Balancing is not Always Good . . . 97--102
             Max B. Webster and   
                  Paul W. Baker   A Class of Differential Equations for
                                  Testing Variable Step-Size Integration   103--107

Information Processing Letters
Volume 22, Number 3, March 3, 1986

          P. Srinivas Kumar and   
                     M. Manohar   On Probability of Forest of Quadtrees
                                  Reducing to Quadtrees  . . . . . . . . . 109--111
              Klaus Ambos-Spies   Inhomogeneities in the polynomial-time
                                  degrees: the degrees of super sparse
                                  sets . . . . . . . . . . . . . . . . . . 113--117
              Franz Aurenhammer   The one-dimensional weighted
                                  Vorono\uìdiagram  . . . . . . . . . . . . 119--123
               Arturo Carpi and   
                   Aldo De Luca   Square-free words of partially
                                  commutative free monoids . . . . . . . . 125--131
                 Yoshio Hattori   Nonisomorphic graphs with the same
                                  $T$-polynomial . . . . . . . . . . . . . 133--134
                        F. Gire   Two decidability problems for infinite
                                  words  . . . . . . . . . . . . . . . . . 135--140
            R. John Muir Hughes   A Novel Representation of Lists and its
                                  Application to the Function `Reverse'    141--144
            Sylvianne R. Schwer   On the rationality of Petri net
                                  languages  . . . . . . . . . . . . . . . 145--146
                       Lin Chen   $O(1)$ space complexity deletion for AVL
                                  trees  . . . . . . . . . . . . . . . . . 147--149
             E. J. Cockayne and   
                  D. E. Hewgill   Exact computation of Steiner Minimal
                                  Trees in the plane . . . . . . . . . . . 151--156
                Robert C. Shock   Computing the minimum cover of
                                  functional dependencies  . . . . . . . . 157--159
                 Michael Kallay   Convex hull made easy  . . . . . . . . . 161--161

Information Processing Letters
Volume 22, Number 4, April 17, 1986

           Brigitte Jaumard and   
                  Michel Minoux   An Efficient Algorithm for the
                                  Transitive Closure and a Linear
                                  Worst-Case Complexity Result for a Class
                                  of Sparse Graphs . . . . . . . . . . . . 163--169
                   J. Mark Keil   Total domination in interval graphs  . . 171--174
                 Wolfgang Panny   A note on the higher moments of the
                                  expected behavior of straight insertion
                                  sort . . . . . . . . . . . . . . . . . . 175--177
                Mark C. Hamburg   Two Tagless Variations on the
                                  Deutsch--Schorr--Waite Algorithm . . . . 179--183
            Michael C. Loui and   
       Teresa A. Matsushita and   
                Douglas B. West   Election in a Complete Network with a
                                  Sense of Direction . . . . . . . . . . . 185--187
                Svante Carlsson   \sc Splitmerge: a fast stable merging
                                  algorithm  . . . . . . . . . . . . . . . 189--192
               B. Codenotti and   
                       G. Lotti   A note on the VLSI counter . . . . . . . 193--195
             Hania Gajewska and   
               Robert E. Tarjan   Deques with heap order . . . . . . . . . 197--200
                  Dana Richards   Data compression and Gray-code sorting   201--205
            Key-Sun S. Choi and   
                  Gil Chang Kim   A Controlled Quantification in Parsing
                                  of Montague Grammar  . . . . . . . . . . 207--216

Information Processing Letters
Volume 22, Number 5, April ??, 1986

                  P. T. Highnam   Optimal Algorithms for Finding the
                                  Symmetries of a Planar Point Set . . . . 219--222
             Shaunak Pawagi and   
             I. V. Ramakrishnan   An $O(\log n)$ algorithm for parallel
                                  update of minimum spanning trees . . . . 223--229
                    Ming Li and   
                   Yaacov Yesha   String-Matching Cannot Be Done by a
                                  Two-Head One-Way Deterministic Finite
                                  Automaton  . . . . . . . . . . . . . . . 231--235
                  John B. Evans   Experiments with Trees for the Storage
                                  and Retrieval of Future Events . . . . . 237--242
                G. K. Gupta and   
                  B. Srinivasan   Approximate storage utilization of
                                  $B$-trees  . . . . . . . . . . . . . . . 243--246
               Paul Bourret and   
           R. Souza de Oliveira   Lower and upper bounds of the sizes of
                                  domains: estimates and experiments . . . 247--253
           Herbert J. Bernstein   Determining the shape of a convex
                                  $n$-sided polygon by using $2n+k$
                                  tactile probes . . . . . . . . . . . . . 255--260
               Arthur M. Keller   Set-Theoretic Problems of Null
                                  Completion in Relational Databases . . . 261--265
            Yannis Manolopoulos   Batched Search of Index Sequential Files 267--272
             Timo O. Alanko and   
               R. L. Smelianski   On the calculation of control transition
                                  probabilities in a program . . . . . . . 273--276

Information Processing Letters
Volume 22, Number 6, May 30, 1986

                Thomas Lickteig   Gaussian elimination is optimal for
                                  solving linear equations in dimension
                                  two  . . . . . . . . . . . . . . . . . . 277--279
           Yoshito Hanatani and   
                   Ronald Fagin   A Simple Characterization of Database
                                  Dependency Implication . . . . . . . . . 281--283
                   Ian Parberry   On recurrent and recursive
                                  interconnection patterns . . . . . . . . 285--289
               Dan Gusfield and   
                   Leonard Pitt   Equivalent approximation algorithms for
                                  node cover . . . . . . . . . . . . . . . 291--294
               Kunio Aizawa and   
                 Akira Nakamura   Direction-independent application of
                                  productions on two-dimensional arrays    295--301
                    Frank Dehne   $O(n^{1/2})$ algorithms for the maximal
                                  elements and ECDF searching problem on a
                                  mesh-connected parallel computer . . . . 303--306
           Krzysztof R. Apt and   
                Dexter C. Kozen   Limits for automatic verification of
                                  finite-state concurrent systems  . . . . 307--309
                R. K. Arora and   
                 S. P. Rana and   
                    M. N. Gupta   Distributed termination detection
                                  algorithm for distributed computations   311--314
                 Sandra Sattolo   An Algorithm to Generate a Random Cyclic
                                  Permutation  . . . . . . . . . . . . . . 315--317
             Ernst L. Leiss and   
            Chamaiporn Jitmedha   Horizontally and vertically bounded
                                  propagation of privileges  . . . . . . . 319--327
                  Tadao Takaoka   An On-Line Pattern Matching Algorithm    329--330


Information Processing Letters
Volume 23, Number 1, July 20, 1986

                Wojciech Rytter   The Space Complexity of the Unique
                                  Decipherability Problem  . . . . . . . . 1--3
            Ferng-Ching Lin and   
                  Wei Kuan Shih   Long edges in the layouts of
                                  shuffle-exchange and cube-connected
                                  cycles graphs  . . . . . . . . . . . . . 5--9
                G. Tinhofer and   
                     H. Schreck   The Bounded Subset Sum Problem is Almost
                                  Everywhere Randomly Decidable in $O(N)$  11--17
                Hartmut Schmeck   On the maximum edge length in VLSI
                                  layouts of complete binary trees . . . . 19--23
 José L. Balcázar   On $\Delta^{\rm P}_2$-immunity . . . . . 25--28
            Karel Culik, II and   
          Juhani Karhumäki   A Note on the Equivalence Problem of
                                  Rational Formal Power Series . . . . . . 29--31
                  K. Kakuta and   
                H. Nakamura and   
                        S. Iida   A Parallel Reference Counting Algorithm  33--37
Bernd-Jürgen J. Falkowski and   
                 Lothar Schmitz   A Note on the Queens' Problem  . . . . . 39--46
                O. M. Vikas and   
          Suresh Kumar Basandra   Data algebra and its application in
                                  database design  . . . . . . . . . . . . 47--54

Information Processing Letters
Volume 23, Number 2, August 20, 1986

       Ivan Lavallée and   
        Gérard Roucairol   A Fully Distributed (Minimal) Spanning
                                  Tree Algorithm . . . . . . . . . . . . . 55--62
             Alberto Apostolico   Improving the worst-case performance of
                                  the Hunt-Szymanski strategy for the
                                  longest common subsequence of two
                                  strings  . . . . . . . . . . . . . . . . 63--69
                   Hans Rohnert   Shortest paths in the plane with convex
                                  polygonal obstacles  . . . . . . . . . . 71--76
             Rob R. Hoogerwoord   An Implementation of Mutual Inclusion    77--80
                Wojciech Rytter   An Application of Mehlhorn's Algorithm
                                  for Bracket Languages to $\log(N)$ Space
                                  Recognition of Input-Driven Languages    81--84
                   Janusz Laski   An Algorithm for the Derivation of
                                  Codefinitions in Computer Programs . . . 85--90
                J. K. Annot and   
             M. D. Janssens and   
              A. J. Van De Goor   Comments on Morris's starvation-free
                                  solution to the mutual exclusion problem
                                  [Inform. Process. Lett. \bf 8(2), 15
                                  February 1979, pp. 76--80] . . . . . . . 91--97
                  Simeon Ntafos   On gallery watchmen in grids . . . . . . 99--102
                    John Franco   On the probabilistic performance of
                                  algorithms for the satisfiability
                                  problem  . . . . . . . . . . . . . . . . 103--106
            Bruno Codenotti and   
                   Grazia Lotti   Area-time tradeoffs for bilinear forms
                                  computations in VLSI . . . . . . . . . . 107--109

Information Processing Letters
Volume 23, Number 3, October 22, 1986

            Bruno Codenotti and   
                   Grazia Lotti   A VLSI Fast Solver for Tridiagonal
                                  Linear Systems . . . . . . . . . . . . . 111--114
                  O. M. Makarov   A Noncommutative Algorithm for
                                  Multiplying $5 \times 5$ Matrices Using
                                  102 Multiplications  . . . . . . . . . . 115--117
           Ten-Hwang H. Lai and   
                   Alan Sprague   A Note on Anomalies in Parallel
                                  Branch-And-Bound Algorithms with
                                  One-To-One Bounding Functions  . . . . . 119--122
                Jack Cooper and   
                   Selim G. Akl   Efficient selection on a binary tree . . 123--126
            Patricio V. Poblete   Approximating functions by their Poisson
                                  transform  . . . . . . . . . . . . . . . 127--130
               Alan A. Bertossi   Total domination in interval graphs  . . 131--134
           Wojciech Szpankowski   On an asymptotic analysis of a tree-type
                                  algorithm for broadcast communications   135--142
                Klaus W. Wagner   On the intersection of the class of
                                  linear context-free languages and the
                                  class of single-reset languages  . . . . 143--146
                   G. Mints and   
                       E. Tyugu   Semantics of a declarative language  . . 147--151
                   Kazem Taghva   Some characterizations of finitely
                                  specifiable implicational dependency
                                  families . . . . . . . . . . . . . . . . 153--158
              Jan Tijmen Udding   Absence of individual starvation using
                                  weak semaphores  . . . . . . . . . . . . 159--162
                  R. B. Tan and   
                     G. Tel and   
                 J. van Leeuwen   Comments on: ``Distributed termination
                                  detection algorithm for distributed
                                  computations'' [Inform. Process. Lett.
                                  \bf 22 (1986), no. 6, 311--314; MR
                                  87j:68034a] by R. K. Arora, S. P. Rana
                                  and M. N. Gupta  . . . . . . . . . . . . 163--163

Information Processing Letters
Volume 23, Number 4, November 8, 1986

               Patrick Dehornoy   Turing complexity of the ordinals  . . . 167--170
                 M. Latteux and   
                   E. Timmerman   Finitely Generated $\omega$-Languages    171--175
               Bowen Alpern and   
             Alan J. Demers and   
              Fred B. Schneider   Safety without stuttering  . . . . . . . 177--180
        David R. O'Hallaron and   
          Paul F. Reynolds, Jr.   A Generalized Deadlock Predicate . . . . 181--188
                    Lenore Blum   Towards an asymptotic analysis of
                                  Karmarkar's algorithm  . . . . . . . . . 189--194
           Alan A. Bertossi and   
         Maurizio A. Bonuccelli   Hamiltonian circuits in interval graph
                                  generalizations  . . . . . . . . . . . . 195--200
            Susumu Yamasaki and   
                  Shuji Doshita   Resolution deduction to detect
                                  satisfiability for another class
                                  including non-Horn sentences in
                                  propositional logic  . . . . . . . . . . 201--207
                     Dan Gordon   Eliminating the flag in threaded binary
                                  search trees . . . . . . . . . . . . . . 209--214
               O. J. Murphy and   
                   S. M. Selkow   The Efficiency of Using $k$-$d$ Trees
                                  for Finding Nearest Neighbors in
                                  Discrete Space . . . . . . . . . . . . . 215--218
                   R. E. Tarjan   Corrigendum: ``Sensitivity analysis of
                                  minimum spanning trees and shortest path
                                  trees'' [Inform. Process. Lett. \bf
                                  14(1), 27 March 1982, pp. 30--33]  . . . 219--219

Information Processing Letters
Volume 23, Number 5, November 24, 1986

            R. Sommerhalder and   
           S. C. Van Westrhenen   A Parallel ${O}(\log n)$ Algorithm for
                                  the Drawing of Algebraic Curves in an $n
                                  \times n$ Square . . . . . . . . . . . . 221--226
              Klaus Ambos-Spies   A Note on Complete Problems for
                                  Complexity Classes . . . . . . . . . . . 227--230
Jan L. A. Van de Snepscheut and   
              Jan Tijmen Udding   An Alternative Implementation of
                                  Communication Primitives . . . . . . . . 231--238
           David John Evans and   
                Nadia Y. Yousif   Merging by the parallel jump searching
                                  algorithm  . . . . . . . . . . . . . . . 239--246
                    G. Chen and   
                 M. H. Williams   The Value of an Array Facility in Prolog 247--251
                   Manfred Broy   Denotational semantics of communicating
                                  sequential programs  . . . . . . . . . . 253--259
             Jordan Stojanovski   A note on implementing Prolog in Lisp    261--264
                  C. C. Handley   An in situ distributive sort . . . . . . 265--270
             Erkki Mäkinen   A Note on Pure Grammars  . . . . . . . . 271--274

Information Processing Letters
Volume 23, Number 6, December 3, 1986

                 Ernst L. Leiss   The Inaccessible Set: a Classification
                                  by Query Type of Security Risks in
                                  Statistical Databases  . . . . . . . . . 275--279
           Mich\`ele Benois and   
            Jacques Sakarovitch   On the Complexity of Some Extended Word
                                  Problems Defined by Cancellation Rules   281--287
       Herbert Edelsbrunner and   
                      Emo Welzl   Halfplanar range search in linear space
                                  and ${O}(n^{0.695})$ query time  . . . . 289--293
                Alain J. Martin   A New Generalization of Dekker's
                                  Algorithm for Mutual Exclusion . . . . . 295--297
             Leszek Holenderski   The Correctness of Nondeterministic
                                  Programs Revisited . . . . . . . . . . . 299--303
              Lloyd Allison and   
                  Trevor I. Dix   A Bit-String Longest-Common-Subsequence
                                  Algorithm  . . . . . . . . . . . . . . . 305--310
          Kwang-Moo M. Choe and   
             Chun-Hyon H. Chang   Efficient computation of the locally
                                  least-cost insertion string for the LR
                                  error repair . . . . . . . . . . . . . . 311--316
               Frank Harary and   
                Peter J. Slater   A Linear Algorithm for the Cutting
                                  Center of a Tree . . . . . . . . . . . . 317--319
            Richard B. Kieburtz   When chasing your tail saves time graph
                                  theory . . . . . . . . . . . . . . . . . 321--324
                Ikuo Nakata and   
                 Masataka Sassa   L-attributed LL(1)-grammars are
                                  LR-attributed  . . . . . . . . . . . . . 325--328


Information Processing Letters
Volume 24, Number 1, January 15, 1987

    Athanasios Alexandrakis and   
             Symeon Bozapalidis   Weighted grammars and Kleene's theorem   1--4
            Stuart A. Kurtz and   
       Michael J. O'Donnell and   
                 James S. Royer   How to prove representation-independent
                                  independence results . . . . . . . . . . 5--10
            W. H. J. Feijen and   
      A. J. M. Van Gasteren and   
                    David Gries   In-situ inversion of a cyclic
                                  permutation  . . . . . . . . . . . . . . 11--14
                 Taenam Kim and   
             Kyung-Yong Y. Chwa   An ${O}(n \log n \log \log n)$ Parallel
                                  Maximum Matching Algorithm for Bipartite
                                  Graphs . . . . . . . . . . . . . . . . . 15--17
               Peter Hochschild   Multiple cuts, input repetition, and
                                  VLSI complexity  . . . . . . . . . . . . 19--24
             Raphael Finkel and   
                Hari H. Madduri   An Efficient Deadlock Avoidance
                                  Algorithm  . . . . . . . . . . . . . . . 25--30
             Masataka Sassa and   
           Harushi Ishizuka and   
                    Ikuo Nakata   ECLR-attributed grammars: a practical
                                  class of LR-attributed grammars  . . . . 31--41
                A. J. Bernstein   Predicate transfer and timeout in
                                  message passing systems  . . . . . . . . 43--52
                 R. S. Bird and   
                    John Hughes   The Alpha-Beta Algorithm: an Exercise in
                                  Program Transformation . . . . . . . . . 53--57
            Toshitsugu Yuba and   
                   Mamoru Hoshi   Binary search networks: a new method for
                                  key searching  . . . . . . . . . . . . . 59--65
                  V. Arvind and   
                      S. Biswas   An ${O}(n^2)$ Algorithm for the
                                  Satisfiability Problem of a Subset of
                                  Propositional Sentences in CNF That
                                  Includes All Horn Sentences  . . . . . . 67--69

Information Processing Letters
Volume 24, Number 2, January 30, 1987

                Maciej Slusarek   An Off-Line Storage Allocation Algorithm 71--75
               E. Allen Emerson   Uniform inevitability is tree automaton
                                  ineffable  . . . . . . . . . . . . . . . 77--79
                    Anne Grazon   An Infinite Word Language Which is Not
                                  co-CFL . . . . . . . . . . . . . . . . . 81--85
                   Ouri Wolfson   Concurrent execution of transaction
                                  copies . . . . . . . . . . . . . . . . . 87--93
                      Dan Field   A note on a new data structure for
                                  in-the-past queries  . . . . . . . . . . 95--96
                Claudio Rey and   
                     Rabab Ward   On determining the on-line minimax
                                  linear fit to a discrete point set in
                                  the plane  . . . . . . . . . . . . . . . 97--101
                   Bogdan Korel   The program dependence graph in static
                                  program testing  . . . . . . . . . . . . 103--108
                  Georg Gottlob   Subsumption and implication  . . . . . . 109--111
             Masataka Sassa and   
                    Ikuo Nakata   A simple realization of LR-parsers for
                                  regular right part grammars  . . . . . . 113--120
           Richard Anderson and   
                  Ernst W. Mayr   Parallelism and the maximal path problem 121--126
             C. A. R. Hoare and   
                      Jifeng He   The weakest prespecification . . . . . . 127--132
         Mihalis Yannakakis and   
              F\uanic\ua Gavril   The maximum $k$-colorable subgraph
                                  problem for chordal graphs . . . . . . . 133--137
               A. K. Pujari and   
                       S. Gupta   Comment on: ``Worst-case choice for the
                                  stable marriage problem'' [Inform.
                                  Process. Lett. \bf 21 (1985), no. 1,
                                  27--30; MR 87b:68081] by D. Kapur and M.
                                  S. Krishnamoorthy  . . . . . . . . . . . 139--139

Information Processing Letters
Volume 24, Number 3, February 13, 1987

                   Marek Kubale   The complexity of scheduling independent
                                  two-processor tasks on dedicated
                                  processors . . . . . . . . . . . . . . . 141--147
                Mark W. Krentel   A note on the transaction backout
                                  problem  . . . . . . . . . . . . . . . . 149--152
              Richard P. Anstee   A polynomial algorithm for
                                  $b$-matchings: an alternative approach   153--157
               M. Roussille and   
                      P. Dufour   Generation of convex polygons with
                                  individual angular constraints . . . . . 159--164
               W. F. McColl and   
                 M. S. Paterson   The planar realization of Boolean
                                  functions  . . . . . . . . . . . . . . . 165--170
              D\~ung T. Hu\`ynh   On solving hard problems by
                                  polynomial-size circuits . . . . . . . . 171--176
                     Dick Grune   How to compare the incomparable  . . . . 177--181
                  M. Castan and   
               M.-H. Durand and   
             M. Lemaî tre   A set of combinators for abstraction in
                                  linear space . . . . . . . . . . . . . . 183--188
      D. C. Van Leijenhorst and   
           Th. P. Van der Weide   On a recursion connected with tree
                                  balancing algorithms . . . . . . . . . . 189--192
                    Varol Akman   An algorithm for determining an opaque
                                  minimal forest of a convex polygon . . . 193--198
                  Michel Raynal   A distributed algorithm to prevent
                                  mutual drift between $n$ logical clocks  199--202
                   Leonard Pitt   A Note on Extending Knuth's Tree
                                  Estimator to Directed Acyclic Graphs . . 203--206
                D. J. Evans and   
                   W. S. Yousif   Explicit solution of block tridiagonal
                                  systems of linear equations  . . . . . . 207--209

Information Processing Letters
Volume 24, Number 4, March ??, 1987

                J. Bazewicz and   
                       G. Finke   Minimizing mean weighted execution time
                                  loss on identical and uniform processors A259--A263
    Jan L. A. Van De Snepscheut   ``Algorithms for on-the-fly garbage
                                  collection'' revisited . . . . . . . . . 211--216
          Shaunak R. Pawagi and   
       P. S. Gopalakrishnan and   
             I. V. Ramakrishnan   Computing dominators in parallel . . . . 217--221
          D. C. Van Leijenhorst   A note on the formula size of the
                                  `$\bmod k$' functions  . . . . . . . . . 223--224
                  M. Zubair and   
                    B. B. Madan   Time efficient systolic architecture for
                                  matrix*vector multiplication . . . . . . 225--231
                 Dario Bini and   
                 Victor Ya. Pan   A logarithmic Boolean time algorithm for
                                  parallel polynomial division . . . . . . 233--237
              Anders Edenbrandt   Chordal graph recognition is in NC . . . 239--241
                Prakash Ramanan   Obtaining lower bounds using artificial
                                  components (fixed order algebraic
                                  decision tree model) . . . . . . . . . . 243--246
                Svante Carlsson   A variant of Heapsort with almost
                                  optimal number of comparisons  . . . . . 247--250
        Martin Charles Golumbic   A general method for avoiding cycling in
                                  a network  . . . . . . . . . . . . . . . 251--253
   Silvio Romero de Lemos Meira   Strict Combinators . . . . . . . . . . . 255--258
            J. B\la\.zewicz and   
                       G. Finke   Minimizing mean weighted execution time
                                  loss on identical and uniform processors 259--263
          R. Nigel Horspool and   
                Michael R. Levy   Correctness of an extended
                                  operator-precedence parsing algorithm    265--273
                  Jonathan Ruby   A liveness property of a parallel
                                  algorithm  . . . . . . . . . . . . . . . 275--277
         Jayme Luiz Szwarcfiter   A note on the computation of the
                                  $k$-closure of a graph . . . . . . . . . 279--280

Information Processing Letters
Volume 24, Number 5, March 16, 1987

             Klaus Madlener and   
                 Friedrich Otto   Using string-rewriting for solving the
                                  word problem for finitely presented
                                  groups . . . . . . . . . . . . . . . . . 281--284
                Takao Asano and   
               Tetsuo Asano and   
                   Hiroshi Imai   Shortest path between two simple
                                  polygons . . . . . . . . . . . . . . . . 285--288
             M. D. Atkinson and   
                    H. W. Chang   Computing the number of mergings with
                                  constraints  . . . . . . . . . . . . . . 289--292
               Cyrus Hazari and   
                  Hussein Zedan   A distributed algorithm for distributed
                                  termination  . . . . . . . . . . . . . . 293--297
                   Gregers Koch   Automating the semantic component  . . . 299--305
           D. S. Hirschberg and   
            Dennis James Volper   Improved Update/Query Algorithms for the
                                  Interval Valuation Problem . . . . . . . 307--310
         Ernest J. H. Chang and   
           Gaston H. Gonnet and   
                    Doron Rotem   On the costs of self-stabilization . . . 311--316
             Mark Valentine and   
                Robert H. Davis   The automated solution of logic puzzles  317--324
              Marek Chrobak and   
                Wojciech Rytter   Remarks on string-matching and one-way
                                  multihead automata . . . . . . . . . . . 325--329
                  R. D. Tennent   A note on undefined expression values in
                                  programming logics . . . . . . . . . . . 331--333
             Peter Widmayer and   
                    Derick Wood   Time- and space-optimal contour
                                  computation for a set of rectangles  . . 335--338
         Michael B. Dillencourt   Traveling salesman cycles are not always
                                  subgraphs of Delaunay triangulations or
                                  of minimum weight triangulations . . . . 339--342
             J. R. Kennaway and   
                    M. R. Sleep   Variable abstraction in $O(n\log n)$
                                  space  . . . . . . . . . . . . . . . . . 343--349

Information Processing Letters
Volume 24, Number 6, April 6, 1987

           Heinrich Müller   Sorting Numbers Using Limited Systolic
                                  Coprocessors . . . . . . . . . . . . . . 351--354
                  Georg Gottlob   On the size of nonredundant FD-covers    355--360
           Andrzej Szepietowski   There are no fully space constructible
                                  functions between $\log \log n$ and
                                  $\log n$ . . . . . . . . . . . . . . . . 361--362
                   Ian Parberry   An improved simulation of space and
                                  reversal bounded deterministic Turing
                                  machines by width and depth bounded
                                  uniform circuits . . . . . . . . . . . . 363--367
                Hanan Samet and   
        Clifford A. Shaffer and   
               Robert E. Webber   Digitizing the plane with cells of
                                  nonuniform size  . . . . . . . . . . . . 369--375
              Anselm Blumer and   
        Andrzej Ehrenfeucht and   
             David Haussler and   
             Manfred K. Warmuth   Occam's Razor  . . . . . . . . . . . . . 377--380
                M. Bajantri and   
            David B. Skillicorn   A fast multiprocessor message passing
                                  implementation . . . . . . . . . . . . . 381--389
      Christopher W. Fraser and   
                David R. Hanson   Optimization of argument evaluation
                                  order  . . . . . . . . . . . . . . . . . 391--395
              Raymond Marie and   
              Kishor S. Trivedi   A note on the effect of preemptive
                                  policies on the stability of a priority
                                  queue  . . . . . . . . . . . . . . . . . 397--401
              William E. Wright   A note on external sorting using almost
                                  single input buffering . . . . . . . . . 403--405
                  M. K. Sridhar   A new algorithm for parallel solution of
                                  linear equations . . . . . . . . . . . . 407--412
       Herbert Edelsbrunner and   
               Mark H. Overmars   Zooming by repeated range detection  . . 413--417


Information Processing Letters
Volume 25, Number 1, April 20, 1987

               Jik H. Chang and   
            Oscar H. Ibarra and   
             Bala Ravikumar and   
                 Leonard Berman   Some observations concerning alternating
                                  Turing machines using small space  . . . 1--9
             Avraham A. Melkman   On-line construction of the convex hull
                                  of a simple polyline . . . . . . . . . . 11--12
               Bernd Kirsig and   
       Klaus-Jörn J. Lange   Separation with the Ruzzo, Simon, and
                                  Tompa relativization implies ${\sc
                                  Dspace}(\log n)\not= {\sc Nspace}(\log
                                  n)$  . . . . . . . . . . . . . . . . . . 13--15
              Richard G. Hamlet   Probable correctness theory  . . . . . . 17--25
           Rodney R. Howell and   
            Louis E. Rosier and   
                   Hsu-Chun Yen   An ${O}(n^{1.5})$ algorithm to decide
                                  boundedness for conflict-free vector
                                  replacement systems  . . . . . . . . . . 27--33
             George Cybenko and   
            David W. Krumme and   
             K. N. Venkataraman   Fixed Hypercube embedding  . . . . . . . 35--39
           Jean-Paul P. Laumond   Obstacle growing in a nonpolygonal world 41--50
                    Joseph Naor   A fast parallel coloring of planar
                                  graphs with five colors  . . . . . . . . 51--53
                Cao An Wang and   
                   Yung H. Tsin   An $O(\log n)$ time parallel algorithm
                                  for triangulating a set of points in the
                                  plane  . . . . . . . . . . . . . . . . . 55--60
             Gary A. Hyslop and   
              Edmund A. Lamagna   Performance of distributive partitioned
                                  sort in a demand paging environment  . . 61--64
                   John H. Reif   A topological approach to dynamic graph
                                  connectivity . . . . . . . . . . . . . . 65--70

Information Processing Letters
Volume 25, Number 2, May 6, 1987

             C. A. R. Hoare and   
                  Jifeng He and   
                  J. W. Sanders   Prespecification in data refinement  . . 71--76
           Jyrki Katajainen and   
            Olli Nevalainen and   
                  Jukka Teuhola   A linear expected-time algorithm for
                                  computing planar relative neighbourhood
                                  graphs . . . . . . . . . . . . . . . . . 77--86
            Mikhail Atallah and   
               Chanderjit Bajaj   Efficient algorithms for common
                                  transversals . . . . . . . . . . . . . . 87--91
                   Manfred Broy   Predicative Specifications for
                                  Functional Programs Describing
                                  Communicating Networks . . . . . . . . . 93--101
           K. B. Lakshmanan and   
               N. Meenakshi and   
                K. Thulasiraman   A time-optimal message-efficient
                                  distributed algorithm for
                                  depth-first-search . . . . . . . . . . . 103--109
                   A. M. Frieze   Parallel algorithms for finding Hamilton
                                  cycles in random graphs  . . . . . . . . 111--117
                F. Miller Maley   An observation concerning
                                  constraint-based compaction  . . . . . . 119--122
            V. J. Rayward-Smith   The complexity of preemptive scheduling
                                  given interprocessor communication
                                  delays . . . . . . . . . . . . . . . . . 123--125
            Ravi B. Boppana and   
         Johan Håstad and   
                 Stathis Zachos   Does co-NP have short interactive
                                  proofs?  . . . . . . . . . . . . . . . . 127--132
                  R. D. Tennent   Quantification in Algol-like languages   133--137
                   G. Mints and   
                       E. Tyugu   Corrigendum: ``Semantics of a
                                  declarative language'' [Inform. Process.
                                  Lett. \bf 23(3), 22 October 1997, pp.
                                  147--151]  . . . . . . . . . . . . . . . 139--139

Information Processing Letters
Volume 25, Number 3, May 29, 1987

               Yoshihito Toyama   Counterexamples to termination for the
                                  direct sum of term rewriting systems . . 141--143
               J. Pierre Verjus   On the proof of a distributed algorithm  145--147
         Michael B. Dillencourt   A non-Hamiltonian, nondegenerate
                                  Delaunay Triangulation . . . . . . . . . 149--151
                 Ten H. Lai and   
                    Tao H. Yang   On distributed snapshots . . . . . . . . 153--158
                 Andrew Klapper   A lower bound on the complexity of the
                                  convex hull problem for simple polyhedra 159--161
                 Ozalp Babaoglu   Stopping times of distributed consensus
                                  protocols: A probabilistic analysis  . . 163--169
                   Satoru Kawai   Local authentication in insecure
                                  environments . . . . . . . . . . . . . . 171--174
         Michael J. Fischer and   
                  Neil Immerman   Interpreting logics of knowledge in
                                  propositional dynamic logic with
                                  converse . . . . . . . . . . . . . . . . 175--181
           Tae-Choong Chung and   
                   Jung-Wan Cho   History sensitive string for multiple
                                  alphabets  . . . . . . . . . . . . . . . 183--188
                      T. H. Tse   On the detection of unstructuredness in
                                  flowgraphs . . . . . . . . . . . . . . . 189--193
              Dieter Zöbel   Transformations for communication
                                  fairness in CSP  . . . . . . . . . . . . 195--198
         N. A. Alexandridis and   
                 P. D. Tsanakas   An Encoding Scheme for the Efficient
                                  Representation of Hierarchical Image
                                  Structures . . . . . . . . . . . . . . . 199--206
               Joseph M. Morris   Varieties of weakest liberal
                                  preconditions  . . . . . . . . . . . . . 207--210

Information Processing Letters
Volume 25, Number 4, June 17, 1987

       Jean-Michel Autebert and   
          Philippe Flajolet and   
         Joaquim Gabarró   Prefixes of infinite words and ambiguous
                                  context-free languages . . . . . . . . . 211--216
          Bettina Brustmann and   
                   Ingo Wegener   The complexity of symmetric functions in
                                  bounded-depth circuits . . . . . . . . . 217--219
               Edward Ochmanski   Inevitability in concurrent systems  . . 221--225
                    Rainer Kemp   A note on the number of leftist trees    227--232
                  J. G. Wiltink   A deficiency of natural deduction  . . . 233--234
             Alberto Apostolico   Remark on the Hsu-Du new algorithm for
                                  the longest common subsequence problem   235--236
                David Gries and   
         Adriano Pascoletti and   
                    Luigi Sbriz   Horner's rule and the computation of
                                  linear recurrences . . . . . . . . . . . 237--240
         Andrew V. Goldberg and   
               Serge A. Plotkin   Parallel ($\delta + 1$)-Coloring of
                                  Constant-Degree Graphs . . . . . . . . . 241--245
           Christos Levcopoulos   An $\Omega(\sqrt{n})$ lower bound for
                                  the nonoptimality of the greedy
                                  triangulation  . . . . . . . . . . . . . 247--251
             Matthias Reichling   A simplified solution of the $N$ queens'
                                  problem  . . . . . . . . . . . . . . . . 253--255
      Anatoli\uì O. Buda   Multiprocessor automata  . . . . . . . . 257--261
           Sandeep N. Bhatt and   
          Stavros S. Cosmadakis   The complexity of minimizing wire
                                  lengths in VLSI layouts  . . . . . . . . 263--267
                   O. Fries and   
                K. Mehlhorn and   
              S. Näher and   
                  A. Tsakalidis   A $\log \log n$ data structure for
                                  three-sided range queries  . . . . . . . 269--273
                Andrew W. Appel   Garbage collection can be faster than
                                  stack allocation . . . . . . . . . . . . 275--279

Information Processing Letters
Volume 25, Number 5, July 10, 1987

             Vijay Raghavan and   
          Shankar M. Venkatesan   On bounds for a board covering problem   281--284
          Jeffrey S. Salowe and   
                  W. L. Steiger   Stable Unmerging in Linear Time and
                                  Constant Space . . . . . . . . . . . . . 285--294
               K. Venkatesh and   
           T. Radhakrishnan and   
                       H. F. Li   Optimal checkpointing and local
                                  recording for domino-free rollback
                                  recovery . . . . . . . . . . . . . . . . 295--303
          Jerzy R. Nawrocki and   
                    J. Martinek   A storage allocation method with
                                  invalidating dangling references . . . . 305--310
                Cristian Calude   Super-exponentials nonprimitive
                                  recursive, but rudimentary . . . . . . . 311--315
                 S. S. Ravi and   
                H. B. Hunt, III   An application of the Planar Separator
                                  Theorem to counting problems . . . . . . 317--321
                David Gries and   
               Ivan Stojmenovic   A Note on Graham's Convex Hull Algorithm 323--327
               Yun Zhou Zhu and   
                  To Yat Cheung   A new distributed breadth-first-search
                                  algorithm  . . . . . . . . . . . . . . . 329--333
                 Rina Suros and   
                    E. Montagne   Fitted diagonals for reducing I/O
                                  bandwidth in systolic systems  . . . . . 335--341
        Stuart A. Friedberg and   
               Gary L. Peterson   An efficient solution to the mutual
                                  exclusion problem using weak semaphores  343--347
                     G. Tel and   
                 J. Van Leeuwen   Comments on ``A distributed algorithm
                                  for distributed termination'' [Inform.
                                  Process. Lett. \bf 24(5), 16 March 1987,
                                  pp. 293--297]  . . . . . . . . . . . . . 349--349

Information Processing Letters
Volume 25, Number 6, July 26, 1987

               Kadri Krause and   
        Lawrence L. Larmore and   
            Dennis James Volper   Packing items from a triangular
                                  distribution . . . . . . . . . . . . . . 351--361
      Joanna J\polhkedrzejowicz   Nesting of shuffle closure is important  363--367
                     Jean Pallo   On the rotation distance in the lattice
                                  of binary trees  . . . . . . . . . . . . 369--373
         Ricardo A. Baeza-Yates   Some average measures in $m$-ary search
                                  trees  . . . . . . . . . . . . . . . . . 375--382
                   Shlomo Moran   Generalized lower bounds derived from
                                  Håstad's main lemma (small depth
                                  circuits)  . . . . . . . . . . . . . . . 383--388
              Manfred Kunde and   
                  Horst Steppat   On the worst-case ratio of a compound
                                  multiprocessor scheduling algorithm  . . 389--396
             Imrich V\vr\softto   The area-time complexity of the VLSI
                                  counter  . . . . . . . . . . . . . . . . 397--400
                       F. Peper   Determining connected components in
                                  linear time by a linear number of
                                  processors . . . . . . . . . . . . . . . 401--406
                     Udo Kelter   The complexity of strict serializability
                                  revisited  . . . . . . . . . . . . . . . 407--411
                Youichi Kobuchi   A note on symmetrical cellular spaces    413--415
          Shaunak R. Pawagi and   
       P. S. Gopalakrishnan and   
             I. V. Ramakrishnan   Corrigendum: ``Computing dominators in
                                  parallel'' . . . . . . . . . . . . . . . 417--417


Information Processing Letters
Volume 26, Number 1, September 15, 1987

           Brigitte Jaumard and   
                  Bruno Simeone   On the complexity of the maximum
                                  satisfiability problem for Horn formulas 1--4
          James R. Driscoll and   
            Sheau-Dong Lang and   
              LeRoy A. Franklin   Modeling $B$-tree insertion activity . . 5--18
               Alfs T. Berztiss   A notation for distributed operations    19--21
               Jean Berstel and   
                 Sre\vcko Brlek   On the length of word chains . . . . . . 23--28
             Ronald V. Book and   
                   Hai-Ning Liu   Rewriting systems and word problems in a
                                  free partially commutative monoid  . . . 29--32
                Svante Carlsson   The Deap --- a Double-Ended Heap to
                                  Implement Double-Ended Priority Queues   33--36
              Janet Incerpi and   
               Robert Sedgewick   Practical variations of Shellsort  . . . 37--43
        Jean Claude Bermond and   
       Jean Michel Fourneau and   
               Alain Jean-Marie   Equivalence of multistage
                                  interconnection networks . . . . . . . . 45--50
     László Babai   Random oracles separate ${\rm PSPACE}$
                                  from the polynomial-time hierarchy . . . 51--53

Information Processing Letters
Volume 26, Number 2, October 19, 1987

         Y. Métivier and   
                   E. Ochmanski   On Lexicographic Semi-Commutations . . . 55--59
               Xiaojun Shen and   
           Herbert Edelsbrunner   A tight lower bound on the size of
                                  visibility graphs  . . . . . . . . . . . 61--64
            Michael Rusinowitch   On termination of the direct sum of
                                  term-rewriting systems . . . . . . . . . 65--70
              Andranik Mirzaian   A halving technique for the longest
                                  stuttering subsequence problem . . . . . 71--75
                     Jan Magott   Performance evaluation of concurrent
                                  systems using conflict-free and
                                  persistent Petri nets  . . . . . . . . . 77--80
                  Zvi Galil and   
                      Moti Yung   Partitioned encryption and achieving
                                  simultaneity by partitioning . . . . . . 81--88
                 C. Mathieu and   
               Claude Puech and   
                  Hossein Yahia   Average efficiency of data structures
                                  for binary image processing  . . . . . . 89--93
          K. G. Subramanian and   
             Rani Siromoney and   
             P. Jeyanthi Abisha   A D0L-T0L public key cryptosystem  . . . 95--97
              Ajay K. Gupta and   
           Susanne E. Hambrusch   Optimal three-dimensional layouts of
                                  complete binary trees  . . . . . . . . . 99--104
    Matthew Thazhuthaveetil and   
                         J. and   
             Andrew R. Pleszkun   On the structural locality of reference
                                  in LISP list access streams  . . . . . . 105--110

Information Processing Letters
Volume 26, Number 3, November 23, 1987

                Andrzej Sza\las   Arithmetical Axiomatization of
                                  First-Order Temporal Logic . . . . . . . 111--116
           O. Sýkora and   
                 I. V\vr\softto   Tight chip area lower bounds for string
                                  matching . . . . . . . . . . . . . . . . 117--119
                 Mingfa Zhu and   
                 Nan K. Loh and   
                       Pepe Siy   Towards the minimum set of primitive
                                  relations in temporal logic  . . . . . . 121--126
                         Y. Hou   Trinity algebra and its application to
                                  machine decompositions . . . . . . . . . 127--134
            A. S. M. Sajeev and   
                   J. Olszewski   Manipulation of data structures without
                                  pointers . . . . . . . . . . . . . . . . 135--143
               Shlomo Moran and   
                Yaron Wolfstahl   Extended impossibility results for
                                  asynchronous complete networks . . . . . 145--151
             Johan Håstad   One-way permutations in ${\rm NC}^0$ . . 153--155
         Michael R. Fellows and   
            Michael A. Langston   Nonconstructive advances in
                                  polynomial-time complexity . . . . . . . 157--162
                    H. Balsters   Comments on: ``A deficiency of natural
                                  deduction'' [Inform. Process. Lett. \bf
                                  25 (1987), no. 4, 233--234; MR
                                  88i:03020a] by J. G. Wiltink . . . . . . 163--164

Information Processing Letters
Volume 26, Number 4, December 4, 1987

                  K. R. Apt and   
           Luc Bougé and   
                   Ph. Clermont   Two normal form theorems for CSP
                                  programs . . . . . . . . . . . . . . . . 165--171
            Michael T. Goodrich   Finding the convex hull of a sorted
                                  point set in parallel  . . . . . . . . . 173--179
                  Ursula Martin   Extension functions for multiset
                                  orderings  . . . . . . . . . . . . . . . 181--186
          Shlomit S. Pinter and   
                Yaron Wolfstahl   Embedding ternary trees in VLSI arrays   187--191
                 U. Guntzer and   
                        M. Paul   Jump interpolation search trees and
                                  symmetric binary numbers . . . . . . . . 193--204
                  Tadao Takaoka   A decomposition rule for the Hoare logic 205--208
         Alberto Apostolico and   
           Susanne E. Hambrusch   Finding maximum cliques on circular-arc
                                  graphs . . . . . . . . . . . . . . . . . 209--215
                 C. Baleanu and   
                     D. Tomescu   An architecture for symbolic processing  217--222

Information Processing Letters
Volume 26, Number 5, January 11, 1988

                  Claudio Arbib   A polynomial characterization of some
                                  graph partitioning problems  . . . . . . 223--230
            Karel Culik, II and   
          Juhani Karhumäki   On totalistic systolic networks  . . . . 231--236
              Andrzej Sieminski   Fast decoding of the Huffman codes . . . 237--241
              Carroll C. Morgan   Data refinement by miracles  . . . . . . 243--246
              Patrick W. Dymond   Input-driven languages are in $\log n$
                                  depth  . . . . . . . . . . . . . . . . . 247--250
    Eljas Soisalon-Soininen and   
                   Jorma Tarhio   Looping LR parsers . . . . . . . . . . . 251--253
             Klaus Hinrichs and   
       Jürg Nievergelt and   
                   Peter Schorn   Plane-sweep solves the closest pair
                                  problem elegantly  . . . . . . . . . . . 255--261
               O. Y. De Vel and   
            E. V. Krishnamurthy   An iterative pipelined array
                                  architecture for the generalized matrix
                                  inversion  . . . . . . . . . . . . . . . 263--267
                Stephen A. Cook   Short propositional formulas represent
                                  nondeterministic computations  . . . . . 269--270
             Erkki Mäkinen   On the rotation distance of binary trees 271--272
                  Joel Seiferas   A Variant of Ben-Or's Lower Bound for
                                  Algebraic Decision Trees . . . . . . . . 273--276

Information Processing Letters
Volume 26, Number 6, January 25, 1988

   Ganesh C. Gopalakrishnan and   
             Mandayam K. Srivas   Implementing functional programs using
                                  mutable abstract data types  . . . . . . 277--286
                  Tat Hung Chan   The boundedness problem for
                                  three-dimensional vector addition
                                  systems with states  . . . . . . . . . . 287--289
             Bruce M. Maggs and   
               Serge A. Plotkin   Minimum-cost spanning tree as a
                                  path-finding problem . . . . . . . . . . 291--293
              Richard John Cole   An optimally efficient selection
                                  algorithm  . . . . . . . . . . . . . . . 295--299
                   Isreal Cidon   Yet another distributed
                                  depth-first-search algorithm . . . . . . 301--305
           Rolf G. Karlsson and   
               Mark H. Overmars   Normalized divide-and-conquer: a scaling
                                  technique for solving multi-dimensional
                                  problems . . . . . . . . . . . . . . . . 307--312
                   Ludwik Czaja   Cause-effect structures  . . . . . . . . 313--319
                 Marc Bezem and   
                Jan Van Leeuwen   On estimating the complexity of
                                  logarithmic decompositions . . . . . . . 321--324
           John Russell Gilbert   Some nested dissection order is nearly
                                  optimal  . . . . . . . . . . . . . . . . 325--328


Information Processing Letters
Volume 27, Number 1, February 15, 1988

            M. Balakrishnan and   
               S. Sutarwala and   
             A. K. Majumdar and   
              D. K. Banerji and   
              J. G. Linders and   
                 J. C. Majithia   A semantic approach for modular
                                  synthesis of VLSI systems  . . . . . . . 1--7
                        Ming Li   A separator theorem for one-dimensional
                                  graphs under linear mapping  . . . . . . 9--11
         Mikhail J. Atallah and   
       Greg N. Frederickson and   
                S. Rao Kosaraju   Sorting with efficient use of
                                  special-purpose sorters  . . . . . . . . 13--15
              G. Ramalingam and   
                C. Pandu Rangan   Total domination in interval graphs
                                  revisited  . . . . . . . . . . . . . . . 17--21
                    Gordon Lyon   A tagless marking that is linear over
                                  subtrees . . . . . . . . . . . . . . . . 23--28
                Mark B. Josephs   The data refinement calculator for $Z$
                                  specifications . . . . . . . . . . . . . 29--33
                    Douglas Lea   Digital and Hilbert ${K}$-${D}$ Trees    35--41
            Alan M. Gibbons and   
               Amos Israeli and   
                Wojciech Rytter   Parallel $O(\log n)$ time edge-colouring
                                  of trees and Halin graphs  . . . . . . . 43--51
               Jik H. Chang and   
            Oscar H. Ibarra and   
                 Bala Ravikumar   Erratum: ``Some observations concerning
                                  alternating Turing machines using small
                                  space'' [Inform. Process. Lett. \bf 25
                                  (1987), no. 1, 1--9; MR 88e:68026] by
                                  the authors and L. Berman  . . . . . . . 53--53

Information Processing Letters
Volume 27, Number 2, February 29, 1988

              Bogdan S. Chlebus   A parallel bucket sort . . . . . . . . . 57--61
                 Jacek Witaszek   A practical method for finding the
                                  optimum postponement transformation for
                                  LR(k) parsers  . . . . . . . . . . . . . 63--67
             Mukesh Singhal and   
                   Yelena Yesha   A polynomial algorithm for computation
                                  of the probability of conflicts in a
                                  database under arbitrary data access
                                  distribution . . . . . . . . . . . . . . 69--74
                  Satoru Miyano   A parallelizable lexicographically first
                                  maximal edge- induced subgraph problem   75--78
                C. C. Chang and   
                    C. H. Chang   An Ordered Minimal Perfect Hashing
                                  Scheme with Single Parameter . . . . . . 79--83
                  Robin Liu and   
                  Simeon Ntafos   On decomposing polygons into uniformly
                                  monotone parts . . . . . . . . . . . . . 85--89
                   Franz Baader   A note on unification type zero  . . . . 91--93
          Ravinderpal S. Sandhu   Cryptographic implementation of a tree
                                  hierarchy for access control . . . . . . 95--98
      Nicholas J. Patterson and   
             Kenneth J. Supowit   Finding the vertices nearest to a point
                                  in a hypercube . . . . . . . . . . . . . 99--102
                 Alan M. Frieze   On the random construction of heaps  . . 103--109

Information Processing Letters
Volume 27, Number 3, March 25, 1988

         Leszek Holenderski and   
                Andrzej Sza\las   Propositional description of finite
                                  cause-effect structures  . . . . . . . . 111--117
           David S. Johnson and   
         Mihalis Yannakakis and   
      Christos H. Papadimitriou   On generating all maximal independent
                                  sets . . . . . . . . . . . . . . . . . . 119--123
                  Kurt Mehlhorn   A faster approximation algorithm for the
                                  Steiner problem in graphs  . . . . . . . 125--128
            Sharat Chandran and   
               Azriel Rosenfeld   Order statistics on a hypercube  . . . . 129--132
               Alan A. Bertossi   Parallel circle-cover algorithms . . . . 133--139
            Stephen A. Cook and   
                   Michael Luby   A simple parallel algorithm for finding
                                  a satisfying truth assignment to a
                                  $2$-CNF formula  . . . . . . . . . . . . 141--145
                Joel Berman and   
                 Willem J. Blok   Positive Boolean dependencies  . . . . . 147--150
                 Osamu Watanabe   On hardness of one-way functions . . . . 151--157
        Jacek Leszczylowski and   
            Staffan Bonnier and   
              Jan Maluszy\'nski   Logic programming with external
                                  procedures: introducing $S$-unification  159--165

Information Processing Letters
Volume 27, Number 4, April 8, 1988

                Yung Hyang Tsin   On Handling Vertex Deletion in Updating
                                  Minimum Spanning Trees . . . . . . . . . 167--168
           K. V. S. Ramarao and   
               Robert Daley and   
                    Rami Melhem   Message complexity of the set
                                  intersection problem . . . . . . . . . . 169--174
                   Hans Rohnert   Time and space efficient algorithms for
                                  shortest paths between convex polygons   175--179
                Richard Koo and   
                      Sam Toueg   Effects of message loss on the
                                  termination of distributed protocols . . 181--188
              Ulrich Faigle and   
                Rainer Schrader   On the convergence of stationary
                                  distributions in simulated annealing
                                  algorithms . . . . . . . . . . . . . . . 189--194
   Abdol Hossein Esfahanian and   
                S. Louis Hakimi   On computing a conditional
                                  edge-connectivity of a graph . . . . . . 195--199
           Andrzej Szepietowski   Remarks on languages acceptable in $\log
                                  \log n$ space  . . . . . . . . . . . . . 201--203
D. Roelants van Baronaigien and   
                   Frank Ruskey   Generating $t$-ary Trees in ${A}$-Order  205--213
          Khaled M. Bugrara and   
                 Paul W. Purdom   An exponential lower bound for the pure
                                  literal rule . . . . . . . . . . . . . . 215--219

Information Processing Letters
Volume 27, Number 5, April 28, 1988

                   Carla Savage   Recognizing majority on a one-way mesh   221--225
               Hermann Jung and   
                  Kurt Mehlhorn   Parallel algorithms for computing
                                  maximal independent sets in trees and
                                  for updating minimum spanning trees  . . 227--236
               T. Krishnaprasad   On the computability of circumscription  237--243
                   Bob P. Weems   A study of page arrangements for
                                  extendible hashing . . . . . . . . . . . 245--248
                Ashok Kumar and   
                 V. M. Malhotra   A new computation rule for Prolog  . . . 249--252
                 Kozo Itano and   
                Yutaka Sato and   
               Hidemi Hirai and   
             Tomoyoshi Yamagata   An incremental pattern matching
                                  algorithm for the pipelined lexical
                                  scanner  . . . . . . . . . . . . . . . . 253--258
            Harold N. Gabow and   
               Robert E. Tarjan   A linear-time algorithm for finding a
                                  minimum spanning pseudoforest  . . . . . 259--263
        Mirko K\vrivánek   The complexity of ultrametric partitions
                                  on graphs  . . . . . . . . . . . . . . . 265--270
              G. Ramalingam and   
                C. Pandu Rangan   A unified approach to domination
                                  problems on interval graphs  . . . . . . 271--274

Information Processing Letters
Volume 27, Number 6, May 13, 1988

       Ji\vrí Matou\vsek   Line arrangements and range search . . . 275--280
               Aldo de Luca and   
             Stefano Varricchio   On the factors of the Thue--Morse word
                                  on three symbols . . . . . . . . . . . . 281--285
             Hans L. Bodlaender   A better lower bound for distributed
                                  leader finding in bidirectional,
                                  asynchronous rings of processors . . . . 287--290
                Meichun Hsu and   
              Stuart E. Madnick   Shifting timestamps for concurrency
                                  control in an information hierarchy  . . 291--297
                    Shay Kutten   Optimal fault-tolerant distributed
                                  construction of a spanning forest  . . . 299--307
                  Ewa Or\lowska   Proof System for Weakest
                                  Prespecification . . . . . . . . . . . . 309--313
                  M. A. Sridhar   On the connectivity of the De Bruijn
                                  graph  . . . . . . . . . . . . . . . . . 315--318
                  Xiaoqiu Huang   A lower bound for the edit-distance
                                  problem under an arbitrary cost function 319--321
    David Fernández-Baca   Nonserial dynamic programming
                                  formulations of satisfiability . . . . . 323--326
                    M. Sakkinen   Comments on ``Manipulation of data
                                  structures without pointers'' [Inform.
                                  Process. Lett. \bf 26(3), 23 November
                                  1997, pp. 135--143]  . . . . . . . . . . 327--328


Information Processing Letters
Volume 28, Number 1, May 30, 1988

                 M. Latteux and   
                   E. Timmerman   Bifaithful starry transductions  . . . . 1--4
           Giuseppe F. Italiano   Finding paths and deleting edges in
                                  directed acyclic graphs  . . . . . . . . 5--11
           Wojciech Szpankowski   The evaluation of an alternative sum
                                  with applications to the analysis of
                                  some data structures . . . . . . . . . . 13--19
              David A. Lamb and   
                    Robin Dawes   Testing for class membership in
                                  multi-parent hierarchies . . . . . . . . 21--25
    José D. P. Rolim and   
             Sheila A. Greibach   On the IO-complexity and approximation
                                  languages  . . . . . . . . . . . . . . . 27--31
      Joanna J\polhkedrzejowicz   Infinite Hierarchy of Expressions
                                  Containing Shuffle Closure Operator  . . 33--37
              Wei-Pang Chin and   
                  Simeon Ntafos   Optimum watchman routes  . . . . . . . . 39--44
                  Andrew Dwelly   Synchronizing the I/O behavior of
                                  functional programs with feedback  . . . 45--51
                 Stephan Olariu   Paw-Free Graphs  . . . . . . . . . . . . 53--54

Information Processing Letters
Volume 28, Number 2, June 24, 1988

            Walter W. Kirchherr   Transportation of an $l \times l$ Matrix
                                  Requires $\Omega(\log l)$ Reversals on
                                  Conservative Turing Machines . . . . . . 55--59
               Hillel Gazit and   
                 Gary L. Miller   An improved parallel algorithm that
                                  computes the BFS numbering of a directed
                                  graph  . . . . . . . . . . . . . . . . . 61--65
                Frank Dehne and   
             Ivan Stojmenovi\'c   An ${O}(\sqrt{n})$ time algorithm for
                                  the ECDF searching problem for arbitrary
                                  dimensions on a mesh-of-processors . . . 67--70
                     Victor Pan   Computing the determinant and the
                                  characteristic polynomial of a matrix
                                  via solving linear systems of equations  71--75
           Joost Engelfriet and   
          Hendrik Jan Hoogeboom   Prefix and equality languages of
                                  rational functions are co-context-free   77--79
            Daniel P. Bovet and   
             S. De Agostino and   
                   R. Petreschi   Parallelism and the feedback vertex set
                                  problem  . . . . . . . . . . . . . . . . 81--85
                   Yves Auffray   Linear strategy for propositional modal
                                  resolution . . . . . . . . . . . . . . . 87--92
              Jürgen Ebert   Computing Eulerian trails  . . . . . . . 93--97
          James H. Anderson and   
               Mohamed G. Gouda   Atomic semantics of nonatomic programs   99--103
       Catherine A. Schevon and   
           Jeffrey Scott Vitter   A parallel algorithm for recognizing
                                  unordered depth-first search . . . . . . 105--110

Information Processing Letters
Volume 28, Number 3, July 4, 1988

            Alexandre Brandwajn   Load imbalance in DASD dynamic
                                  reconnection . . . . . . . . . . . . . . 111--119
                 Prateek Mishra   Strictness Analysis of the Untyped
                                  $\lambda$-Calculus . . . . . . . . . . . 121--125
          J. Aguilar-Martin and   
                  Claudi Alsina   Characterizations of some rescaling
                                  functions  . . . . . . . . . . . . . . . 127--132
           Mark Allen Weiss and   
               Robert Sedgewick   Bad cases for Shaker-sort  . . . . . . . 133--136
               John F. Morrison   Parallel $p$-adic computation  . . . . . 137--140
            Fabrizio Luccio and   
           A. Pietracaprina and   
                       G. Pucci   A probabilistic simulation of PRAMs on a
                                  bounded degree network . . . . . . . . . 141--147
                 M. Y. Chan and   
                    W. L. Chung   Optimal multidisk partial match file
                                  designs  . . . . . . . . . . . . . . . . 149--155
                 Hasan Ural and   
                        Bo Yang   A structural test selection criterion    157--163

Information Processing Letters
Volume 28, Number 4, July 29, 1988

  Colm Ó'Dúnlaing   A tight lower bound for the complexity
                                  of path-planning for a disc  . . . . . . 165--170
               Makoto Imase and   
               Yoshifumi Manabe   Fault-Tolerant Routings in a
                                  $\kappa$-Connected Network . . . . . . . 171--175
            Moon Jung Chung and   
           M. S. Krishnamoorthy   Algorithms of placing recovery points    177--181
               Jianzhong Du and   
          Joseph Y.-T. T. Leung   Scheduling tree-structured tasks with
                                  restricted execution times . . . . . . . 183--188
      Daniel J. Rosenkrantz and   
             Harry B. Hunt, III   Matrix multiplication for finite
                                  algebraic systems  . . . . . . . . . . . 189--192
                    Yuji Takada   Grammatical Inference for Even Linear
                                  Languages Based on Control Sets  . . . . 193--199
              Guan-Ing Chen and   
                  Ten Hwang Lai   Preemptive scheduling of independent
                                  jobs on a hypercube  . . . . . . . . . . 201--206
            Gilles Brassard and   
                 Sampath Kannan   The generation of random permutations on
                                  the fly  . . . . . . . . . . . . . . . . 207--212
                  Ichiro Suzuki   Proving properties of a ring of
                                  finite-state machines  . . . . . . . . . 213--214
             Katsushi Inoue and   
                 Itsuo Takanami   Some considerations about ${\rm
                                  NPRIORITY(1)}$ without ROM . . . . . . . 215--219

Information Processing Letters
Volume 28, Number 5, August 12, 1988

            Antoni Mazurkiewicz   Solvability of the asynchronous ranking
                                  problem  . . . . . . . . . . . . . . . . 221--224
             Ananth V. Iyer and   
          H. Donald Ratliff and   
                     G. Vijayan   Optimal node ranking of trees  . . . . . 225--229
                  Don Platt and   
                Moneeb A. Magdy   Adaptive control using switched
                                  capacitor filters  . . . . . . . . . . . 231--234
             Shuo-Yen Robert Li   Reconstruction of polygons from
                                  projections  . . . . . . . . . . . . . . 235--240
          Howard J. Karloff and   
           Ramamohan Paturi and   
                    Janos Simon   Universal traversal sequences of length
                                  $n^{O(\log n)}$ for cliques  . . . . . . 241--243
    Jean-François Romeuf   Shortest path under rational constraint  245--248
              Lance Fortnow and   
                 Michael Sipser   Are there interactive protocols for
                                  CO-NP languages? . . . . . . . . . . . . 249--251
              Paolo Ciaccia and   
                 Dario Maio and   
                  Paolo Tiberio   A unifying approach to evaluating block
                                  accesses in database organizations . . . 253--257
                  P. K. Das and   
                   D. Q. M. Fay   Fault-tolerant and flexible
                                  interconnection of multiple processors   259--268
           Leslie L. Miller and   
                S. K. Gadia and   
                 S. Kothari and   
                      K. C. Liu   Completeness issues for join
                                  dependencies derived from the universal
                                  relation join dependency . . . . . . . . 269--274

Information Processing Letters
Volume 28, Number 6, August 29, 1988

               Alan A. Bertossi   On the domatic number of interval graphs 275--280
                 D. W. Wang and   
                    Yue-Sun Kuo   A study on two geometric location
                                  problems . . . . . . . . . . . . . . . . 281--286
                 K. Vidyasankar   Converting Lamport's regular register to
                                  atomic register  . . . . . . . . . . . . 287--290
            Juris Hartmanis and   
               Lane Hemachandra   On sparse oracles separating feasible
                                  complexity classes . . . . . . . . . . . 291--295
              Gen-Huey Chen and   
                   M. S. Yu and   
                      L. T. Liu   Two algorithms for constructing a binary
                                  tree from its traversals . . . . . . . . 297--299
                Chin Wen Ho and   
              Richard C. T. Lee   Efficient parallel algorithms for
                                  finding maximal cliques, clique trees,
                                  and minimum coloring on chordal graphs   301--309
        Maciej Li\'skiewicz and   
              Krzysztof Lory\'s   Alternating real-time computations . . . 311--316
          Edward P. F. Chan and   
            Hector J. Hernandez   Testing unboundedness of database
                                  schemes and functional dependencies  . . 317--326
            Michael C. Loui and   
       Teresa A. Matsushita and   
                Douglas B. West   Corrigendum: ``Election in a Complete
                                  Network with a Sense of Direction''
                                  [Inform. Process. Lett. \bf 22(4), 17
                                  April 1986, pp. 185--187]  . . . . . . . 327--327


Information Processing Letters
Volume 29, Number 1, September 15, 1988

                  Michel Minoux   LTUR: a simplified linear-time unit
                                  resolution algorithm for Horn formulae
                                  and computer implementation  . . . . . . 1--12
              Shing Tsaan Huang   A fully distributed termination
                                  detection scheme . . . . . . . . . . . . 13--18
             Jean-Claude Raoult   Proving open properties by induction . . 19--23
             Matthias Reichling   On the detection of a common
                                  intersection of $k$ convex objects in
                                  the plane  . . . . . . . . . . . . . . . 25--29
           F. Warren Burton and   
              G. P. McKeown and   
            V. J. Rayward-Smith   On process assignment in parallel
                                  computing  . . . . . . . . . . . . . . . 31--34
                  Erkki Makinen   On linear search heuristics  . . . . . . 35--36
        Michael D. Atkinson and   
                     N. Santoro   A practical algorithm for Boolean matrix
                                  multiplication . . . . . . . . . . . . . 37--38
               J. L. W. Kessels   An exercise in proving
                                  self-stabilization with a variant
                                  function . . . . . . . . . . . . . . . . 39--42
             Masataka Sassa and   
                    Ikuo Nakata   Time-optimal short-circuit evaluation of
                                  Boolean expressions  . . . . . . . . . . 43--51
                R. K. Arora and   
                    M. N. Gupta   More comments on: ``Distributed
                                  termination detection algorithm for
                                  distributed computations'' [Arora, Gupta
                                  and S. P. Rana, Inform. Process. Lett.
                                  \bf 22 (1986), no. 6, 311--314; R. B.
                                  Tan, G. Tel and J. van Leeuwen, ibid.
                                  \bf 23 (1986), no. 3, 163; MR 87j:68034a
                                  b] . . . . . . . . . . . . . . . . . . . 53--55

Information Processing Letters
Volume 29, Number 2, September 30, 1988

        André Arnold and   
                  Paul Crubille   A linear algorithm to solve fixed-point
                                  equations on transition systems  . . . . 57--66
                Andrzej Sza\las   An incompleteness result in Process
                                  Algebra  . . . . . . . . . . . . . . . . 67--70
                Wojciech Rytter   On efficient parallel computations of
                                  costs of paths on a grid graph . . . . . 71--74
             Frank Hoffmann and   
                  Klaus Kriegel   Embedding rectilinear graphs in linear
                                  time . . . . . . . . . . . . . . . . . . 75--79
                 Andrzej Blikle   A guided tour of the mathematics of
                                  MetaSoft '88 . . . . . . . . . . . . . . 81--86
        Dietmar Wätjen and   
                    Erwin Unruh   On the degree of synchronization of
                                  $k\,$lT0L and $k\,$lET0L systems . . . . 87--89
               Aldo de Luca and   
    Mariacristina Pelagalli and   
             Stefano Varricchio   Test sets for languages of infinite
                                  words  . . . . . . . . . . . . . . . . . 91--95
               Basile Louka and   
               Maurice Tchuente   Dynamic programming on two-dimensional
                                  systolic arrays  . . . . . . . . . . . . 97--104
            Hari Ballabh Mittal   A fast backtrack algorithm for graph
                                  isomorphism  . . . . . . . . . . . . . . 105--110

Information Processing Letters
Volume 29, Number 3, October 26, 1988

            Oscar H. Ibarra and   
                  Tao Jiang and   
                 Bala Ravikumar   Some subclasses of context-free
                                  languages in ${\rm NC}^1$  . . . . . . . 111--117
             Gregory E. Shannon   A linear-processor algorithm for
                                  depth-first search in planar graphs  . . 119--123
          Paliath Narendran and   
                 Friedrich Otto   Preperfectness is undecidable for Thue
                                  systems containing only length-reducing
                                  rules and a single commutation rule  . . 125--130
               Gottfried Vossen   A new characterization of FD implication
                                  with an application to update anomalies  131--135
             Hans L. Bodlaender   The complexity of finding uniform
                                  emulations on fixed graphs . . . . . . . 137--141
            P. M. Van Den Broek   Confluence of indirection reductions in
                                  graph rewrite systems  . . . . . . . . . 143--148
                  S. Haldar and   
              D. K. Subramanian   Ring based termination detection
                                  algorithm for distributed computations   149--153
               Bogdan Korel and   
                   Janusz Laski   Dynamic program slicing  . . . . . . . . 155--163

Information Processing Letters
Volume 29, Number 4, November 12, 1988

          Jerzy R. Nawrocki and   
               Andrzej Urbanski   Fixed-sized blocks optimization  . . . . 165--169
         Symeon Bozapalidis and   
               Stavros Ioulidis   Varieties of formal series on trees and
                                  Eilenberg's theorem  . . . . . . . . . . 171--175
                   Sang Cho and   
              D\~ung T. H\`uynh   On a complexity hierarchy between ${\rm
                                  L}$ and ${\rm NL}$ . . . . . . . . . . . 177--182
             Mohamed Ouksel and   
              Peter Scheuermann   Implicit data structures for linear
                                  hashing schemes  . . . . . . . . . . . . 183--189
               Chan-Ik Park and   
                Kyu Ho Park and   
                  Myunghwan Kim   Efficient backward execution in AND/OR
                                  process model  . . . . . . . . . . . . . 191--198
                 Ernst L. Leiss   On the degree of dominator trees . . . . 199--200
        F. E. J. Kruseman Aretz   On a recursive ascent parser . . . . . . 201--206
         Fabio A. Schreiber and   
                    G. Rosolini   An algebraic description of some
                                  state-dependent failure mechanisms . . . 207--211
             Sakti Pramanik and   
                  Myoung Ho Kim   HCB tree a height compressed $B$ tree
                                  for parallel processing  . . . . . . . . 213--220

Information Processing Letters
Volume 29, Number 5, November 24, 1988

              Giorgio Gallo and   
        Maria Grazia Scutell\`a   Polynomially solvable satisfiability
                                  problems . . . . . . . . . . . . . . . . 221--227
                     H. J. Boom   Lazy variable-renumbering makes
                                  substitution cheap . . . . . . . . . . . 229--232
                 Boris S. Veroy   Optimal search algorithm for a minimum
                                  of a discrete periodic bimodal function  233--239
                   Peter Schorn   A canonical simplifier for trigonometric
                                  expressions in the kinematic equation    241--246
Füsun Özgüner and   
                     C. Aykanat   A reconfiguration algorithm for fault
                                  tolerance in a hypercube multiprocessor  247--254
              Marek Chrobak and   
                 Richard Harter   A note on random sampling  . . . . . . . 255--256
              William W. McCune   Un-Skolemizing clause sets . . . . . . . 257--263
                   Micha Sharir   The shortest watchtower and related
                                  problems for polyhedral terrains . . . . 265--270
          Alessandro d'Atri and   
               Marina Moscarini   On hypergraph acyclicity and graph
                                  chordality . . . . . . . . . . . . . . . 271--274
                 Pratul Dublish   An $O(n^3)$ algorithm for finding the
                                  minimal opaque forest of a convex
                                  polygon  . . . . . . . . . . . . . . . . 275--276

Information Processing Letters
Volume 29, Number 6, December 8, 1988

      Mila E. Majster-Cederbaum   On the uniqueness of fixed points of
                                  endofunctors in a category of complete
                                  metric spaces  . . . . . . . . . . . . . 277--281
          Bernard M. Waxman and   
                   Makoto Imase   Worst-case performance of
                                  Rayward-Smith's Steiner tree heuristic   283--287
                 Stephan Olariu   On the unimodality of convex polygons    289--292
                 Carroll Morgan   Auxiliary variables in data refinement   293--296
         Ir\`ene Guessarian and   
                    Lutz Priese   On the minimal number of $\times$
                                  operators to model regularity in fair
                                  SCCS . . . . . . . . . . . . . . . . . . 297--300
                David Alex Lamb   Benign side effects  . . . . . . . . . . 301--305
            Narayan Shankar and   
            Vijaya Ramachandran   Efficient parallel circuits and
                                  algorithms for division  . . . . . . . . 307--313
                  Tetsuo Moriya   Closure property of principal cones
                                  under substitution . . . . . . . . . . . 315--317
                 Boris S. Veroy   Average complexity of divide-and-conquer
                                  algorithms . . . . . . . . . . . . . . . 319--326
                 Torben Hagerup   On saving space in parallel computation  327--329


Information Processing Letters
Volume 30, Number 1, January 16, 1989

               M. J. Foster and   
            Ronald I. Greenberg   Lower bounds on the area of finite-state
                                  machines . . . . . . . . . . . . . . . . 1--7
              Jeffrey S. Salowe   $L$-infinity interdistance selection by
                                  parametric search  . . . . . . . . . . . 9--14
                     Peter Roth   A note on word chains and regular
                                  languages  . . . . . . . . . . . . . . . 15--18
                  Ph. Darondeau   Bisimulation and effectiveness . . . . . 19--20
       Ravinderpal Singh Sandhu   The reflected tree hierarchy for
                                  protection and sharing . . . . . . . . . 21--26
             Andrzej Lingas and   
              Marek Karpi\'nski   Subtree isomorphism is NC reducible to
                                  bipartite perfect matching . . . . . . . 27--32
          P. P. Chakrabarti and   
                   S. Ghose and   
                  A. Pandey and   
                S. C. De Sarkar   Increasing search efficiency using
                                  multiple heuristics  . . . . . . . . . . 33--36
       György Turán   Lower bounds for synchronous circuits
                                  and planar circuits  . . . . . . . . . . 37--40
                  Zvi Galil and   
                     Victor Pan   Parallel evaluation of the determinant
                                  and of the inverse of a matrix . . . . . 41--45
Mihály Geréb-Graus and   
           Ramamohan Paturi and   
         Endre Szemerédi   There are no $p$-complete families of
                                  symmetric Boolean functions  . . . . . . 47--49
              Eric C. R. Hehner   Real-time programming  . . . . . . . . . 51--56

Information Processing Letters
Volume 30, Number 2, January 30, 1989

               Rudolf Fleischer   Communication complexity of
                                  multi-processor systems  . . . . . . . . 57--65
            Wing Shing Wong and   
            Robert J. T. Morris   A new approach to choosing initial
                                  points in local search . . . . . . . . . 67--72
            June Hyoung Kim and   
                Kyu Ho Park and   
                  Myunghwan Kim   A model of distributed control:
                                  dependency and uncertainty . . . . . . . 73--77
             Charles Consel and   
                  Olivier Danvy   Partial evaluation of pattern matching
                                  in strings . . . . . . . . . . . . . . . 79--86
                  R. Shonkwiler   An image algorithm for computing the
                                  Hausdorff distance efficiently in linear
                                  time . . . . . . . . . . . . . . . . . . 87--89
                  Milena Mihail   On coupling and the approximation of the
                                  permanent  . . . . . . . . . . . . . . . 91--95
          Charles U. Martel and   
                   Dan Gusfield   A fast parallel quicksort algorithm  . . 97--102
            Peter Van Emde Boas   Space measures for storage modification
                                  machines . . . . . . . . . . . . . . . . 103--110

Information Processing Letters
Volume 30, Number 3, February 13, 1989

               Toshiya Itoh and   
                  Shigeo Tsujii   An efficient algorithm for deciding
                                  quadratic residuosity in finite fields
                                  ${\rm GF}(p^m)$  . . . . . . . . . . . . 111--114
               Matti O. Jokinen   Customizable garbage collectors  . . . . 115--118
                J. Scott Provan   Shortest enclosing walks and cycles in
                                  embedded graphs  . . . . . . . . . . . . 119--125
                 O. Gerstel and   
                 Y. Mansour and   
                        S. Zaks   Bit complexity of order statistics on a
                                  distributed star network . . . . . . . . 127--132
    José D. P. Rolim and   
             Sheila A. Greibach   A note on the best-case complexity . . . 133--138
                     Udo Kelter   The pitfall paradox and its solution
                                  with virtual objects . . . . . . . . . . 139--143
          Jorgen Staunstrup and   
                Jurg Nievergelt   The behavior of shared objects:
                                  concepts, pitfalls, and a new model  . . 145--151
                Karel Culik, II   Variations of the firing squad problem
                                  and applications . . . . . . . . . . . . 153--157
               E. M. Ehlers and   
                S. H. von Solms   Using random context structure grammars
                                  to represent chemical structures . . . . 159--166

Information Processing Letters
Volume 30, Number 4, February 27, 1989

              Christian Lavault   Average number of messages for
                                  distributed leader-finding in rings of
                                  processors . . . . . . . . . . . . . . . 167--176
            Houssine Chetto and   
                Maryline Chetto   Scheduling periodic and sporadic tasks
                                  in a real-time system  . . . . . . . . . 177--184
                  James Wogulis   Self-adjusting and split sequence hash
                                  tables . . . . . . . . . . . . . . . . . 185--188
                  Kerry Raymond   A distributed algorithm for multiple
                                  entries to a critical section  . . . . . 189--193
             Friedemann Mattern   Global quiescence detection based on
                                  credit distribution and recovery . . . . 195--200
          Ronald E. Barkley and   
                    T. Paul Lee   Point representation and hashing of an
                                  interval . . . . . . . . . . . . . . . . 201--203
              Alok Aggarwal and   
            Don Coppersmith and   
                   Dan Kleitman   A generalized model for understanding
                                  evasiveness  . . . . . . . . . . . . . . 205--208
                   J. M. Robson   Separating strings with small automata   209--214
        Joseph C. Culberson and   
                 Piotr Rudnicki   A fast algorithm for constructing trees
                                  from distance matrices . . . . . . . . . 215--220

Information Processing Letters
Volume 30, Number 5, March 13, 1989

                 K. Vidyasankar   An elegant $1$-writer multireader
                                  multivalued atomic register  . . . . . . 221--223
            Wojciech Rytter and   
                Tomasz Szymacha   Parallel algorithms for a class of
                                  graphs generated recursively . . . . . . 225--231
               Lud\vek Ku\vcera   Graphs with small chromatic numbers are
                                  easy to color  . . . . . . . . . . . . . 233--236
           Hock Thiam Ch'ng and   
              B. Srinivasan and   
                  Beng Chin Ooi   Study of self-organizing heuristics for
                                  skewed access patterns . . . . . . . . . 237--244
               Gyuyoun Song and   
             Donghyeon Park and   
               Dongmyun Lee and   
                Kyu Ho Park and   
                  Myunghwan Kim   A distributed deadlock detection
                                  algorithm: distributed graph
                                  reconstruction algorithm . . . . . . . . 245--252
        Yechezkel Zalcstein and   
                     Max Garzon   An ${\rm NC}^2$ algorithm for testing
                                  similarity of matrices . . . . . . . . . 253--254
               Dan Gusfield and   
               Robert W. Irving   Parametric stable marriage and minimum
                                  cuts . . . . . . . . . . . . . . . . . . 255--259
                 Moshe Y. Vardi   A note on the reduction of two-way
                                  automata to one-way automata . . . . . . 261--264
              Vijayan Rajan and   
                R. K. Ghosh and   
                       P. Gupta   An efficient parallel algorithm for
                                  random sampling  . . . . . . . . . . . . 265--268
          Edward Omiecinski and   
                    Eileen Tien   A hash-based join algorithm for a
                                  cube-connected parallel computer . . . . 269--275

Information Processing Letters
Volume 30, Number 6, March 28, 1989

             J. L. Nazareth and   
               K. A. Ariyawansa   On accelerating Newton's method based on
                                  a conic model  . . . . . . . . . . . . . 277--281
               Aldo de Luca and   
             Stefano Varricchio   Factorial languages whose growth
                                  function is quadratically upper bounded  283--288
             Greg Lindhorst and   
               Farhad Shahrokhi   On renaming a set of clauses as a Horn
                                  set  . . . . . . . . . . . . . . . . . . 289--293
            Oscar H. Ibarra and   
                      Tao Jiang   Optimal simulation of tree arrays by
                                  linear arrays  . . . . . . . . . . . . . 295--302
                   Carsten Vogt   A new approach to optimal cache
                                  scheduling . . . . . . . . . . . . . . . 303--310


Information Processing Letters
Volume 31, Number 1, April ??, 1989

                       V. Kotov   Andrei P. Ershov (1931--1988)  . . . . . 1--2
                David Ginat and   
          Daniel D. Sleator and   
               Robert E. Tarjan   A tight amortized bound for path
                                  reversal . . . . . . . . . . . . . . . . 3--5
            Tomihisa Kamada and   
                   Satoru Kawai   An algorithm for drawing general
                                  undirected graphs  . . . . . . . . . . . 7--15
              Alok Aggarwal and   
                   Dina Kravets   A linear time algorithm for finding all
                                  farthest neighbors in a convex polygon   17--20
                Yves Robert and   
        Bernard Tourancheau and   
                 Gilles Villard   Data allocation strategies for the Gauss
                                  and Jordan algorithms on a ring of
                                  processors . . . . . . . . . . . . . . . 21--29
             Richard I. Hartley   Drawing polygons given angle sequences   31--33
                    Vijay Kumar   Concurrency control on extendible
                                  hashing  . . . . . . . . . . . . . . . . 35--41
                  S. Olariu and   
                     J. Randall   Welsh-Powell opposition graphs . . . . . 43--46
                       Sheng Yu   A pumping lemma for deterministic
                                  context-free languages . . . . . . . . . 47--51
        Hubert de Fraysseix and   
                   Hiroshi Imai   Notes on oriented depth-first search and
                                  longest paths  . . . . . . . . . . . . . 53--56

Information Processing Letters
Volume 31, Number 2, April 26, 1989

                  F. Luccio and   
                       L. Pagli   On the upper bound on the rotation
                                  distance of binary trees . . . . . . . . 57--60
             Chin-Wen W. Ho and   
                   R. C. T. Lee   Counting clique trees and computing
                                  perfect elimination schemes in parallel  61--68
                Rajamani Sundar   Worst-case data structures for the
                                  priority queue with attrition  . . . . . 69--75
               J. M. Basart and   
                      L. Huguet   An approximation algorithm for the TSP
                                  (travelling salesman problem)  . . . . . 77--81
              M. V. Ramakrishna   Analysis of random probing hashing . . . 83--90
               F. Warren Burton   A note on higher-order functions versus
                                  logical variables  . . . . . . . . . . . 91--95
                Iain A. Stewart   An algorithm for colouring perfect
                                  planar graphs  . . . . . . . . . . . . . 97--101
                Wojciech Rytter   A note on optimal parallel
                                  transformations of regular expressions
                                  to nondeterministic finite automata  . . 103--109

Information Processing Letters
Volume 31, Number 3, May 8, 1989

           D. B. Skillicorn and   
                  D. T. Barnard   Parallel parsing on the Connection
                                  Machine  . . . . . . . . . . . . . . . . 111--117
           Satoshi Matsuoka and   
            Tomihisa Kamada and   
                   Satoru Kawai   Asymptotic evaluation of window
                                  visibility . . . . . . . . . . . . . . . 119--126
                     G. Tel and   
                     F. Mattern   Comments on ``Ring based termination
                                  detection algorithm for distributed
                                  computations'' [Inform. Process. Lett.
                                  \bf 29(3), 26 October 1988, pp.
                                  149--153]  . . . . . . . . . . . . . . . 127--128
              Wei Kuan Shih and   
                   Wen-Lian Hsu   An $O(n \log n + m \log \log n)$ maximum
                                  weight clique algorithm for circular-arc
                                  graphs . . . . . . . . . . . . . . . . . 129--134
             Hans L. Bodlaender   Achromatic number is NP-complete for
                                  cographs and interval graphs . . . . . . 135--138
             John N. Tsitsiklis   On the use of random numbers in
                                  asynchronous simulation via rollback . . 139--144
             Joseph Y.-T. Leung   Bin packing with restricted piece sizes  145--149
           Patrick Lentfert and   
               Mark H. Overmars   Data structures in a real-time
                                  environment  . . . . . . . . . . . . . . 151--155
                J. Cheriyan and   
               S. N. Maheshwari   The parallel complexity of finding a
                                  blocking flow in a $3$-layer network . . 157--161
                 Martin Beaudry   Characterization of idempotent
                                  transformation monoids . . . . . . . . . 163--166

Information Processing Letters
Volume 31, Number 4, May 22, 1989

                 Angelo Gregori   Unit-length embedding of binary trees on
                                  a square grid  . . . . . . . . . . . . . 167--173
                     Xiaolin Wu   Fast approximations to discrete optimal
                                  quantization . . . . . . . . . . . . . . 175--179
              Bogdan S. Chlebus   Parallel iterated bucket sort  . . . . . 181--183
       Vishv Mohan Malhotra and   
                Tang Van To and   
           Kanchana Kanchanasut   An improved data-dependency-based
                                  backtracking scheme for Prolog . . . . . 185--189
               Sally A. Goldman   A space efficient greedy triangulation
                                  algorithm  . . . . . . . . . . . . . . . 191--196
                   Anujan Varma   Fault-tolerant routing in unique-path
                                  multistage interconnection networks  . . 197--201
             Friedemann Mattern   An efficient distributed termination
                                  test . . . . . . . . . . . . . . . . . . 203--208
            Scott D. Carson and   
               Paul Vongsathorn   Error bounds on disk arrangement using
                                  frequency information  . . . . . . . . . 209--213
          Dorit S. Hochbaum and   
                     Ron Shamir   An $O(n\,\log ^2n)$ algorithm for the
                                  maximum weighted tardiness problem . . . 215--219

Information Processing Letters
Volume 31, Number 5, June 12, 1989

                Prakash Ramanan   Average-case analysis of the smart next
                                  fit algorithm  . . . . . . . . . . . . . 221--225
                   R. Casas and   
                    J. Diaz and   
                 J. M. Steyaert   Average-case analysis of Robinson's
                                  unification algorithm with two different
                                  variables  . . . . . . . . . . . . . . . 227--232
         Manuel E. Bermudez and   
              George Logothetis   Simple computation of LALR(1) lookahead
                                  sets . . . . . . . . . . . . . . . . . . 233--238
                       Tom Head   Deciding the immutability of regular
                                  codes and languages under finite
                                  transductions  . . . . . . . . . . . . . 239--241
                 Stephan Olariu   A simple linear-time algorithm for
                                  computing the RNG and MST of unimodal
                                  polygons . . . . . . . . . . . . . . . . 243--247
                  Samir Khuller   On computing graph closures  . . . . . . 249--255
              Ellen B. Feinberg   Characterizing the shortest path of an
                                  object among obstacles . . . . . . . . . 257--264
         Andrew V. Goldberg and   
               Robert E. Tarjan   A parallel algorithm for finding a
                                  blocking flow in an acyclic network  . . 265--271
 Bernd-Jürgen J. Falkowski   A self-optimizing Prolog program and the
                                  underlying statistical model . . . . . . 273--276

Information Processing Letters
Volume 31, Number 6, June 19, 1989

         Gunnar Stålmarck   A note on the computational complexity
                                  of the pure classical implication
                                  calculus . . . . . . . . . . . . . . . . 277--278
          Hiroshi Nagamochi and   
              Toshihide Ibaraki   On max-flow min-cut and integral flow
                                  properties for multicommodity flows in
                                  directed networks  . . . . . . . . . . . 279--285
             Dean P. Foster and   
                Rakesh V. Vohra   Probabilistic analysis of a heuristics
                                  for the dual bin packing problem . . . . 287--290
                   Serge Yoccoz   Recursive $\omega$-rule for proof
                                  systems  . . . . . . . . . . . . . . . . 291--294
                 Ravi Mukkamala   Some properties of view-based
                                  replication control algorithms for
                                  distributed systems  . . . . . . . . . . 295--298
           Paola Bertolazzi and   
                Antonio Sassano   A decomposition strategy for the vertex
                                  cover problem  . . . . . . . . . . . . . 299--304
                   Ludwik Czaja   Finite processes in cause-effect
                                  structures and their composition . . . . 305--310
              Alok Aggarwal and   
              Michael Hawrylycz   On computing the closest boundary point
                                  on the convex hull . . . . . . . . . . . 311--314
            Svante Carlsson and   
               Jingsen Chen and   
              Thomas Strothotte   A note on the construction of the data
                                  structure ``deap'' . . . . . . . . . . . 315--317
          Peter A. Bloniarz and   
                     S. S. Ravi   An $\Omega (n \log n)$ lower bound for
                                  decomposing a set of points into chains  319--322
               Norbert Eisinger   A note on the completeness of resolution
                                  without self-resolution  . . . . . . . . 323--326
                  Lloyd Allison   Direct semantics and exceptions define
                                  jumps and coroutines . . . . . . . . . . 327--330


Information Processing Letters
Volume 32, Number 1, July 3, 1989

                Peter Damaschke   The Hamiltonian circuit problem for
                                  circle graphs is NP-complete . . . . . . 1--2
               Dilip Sarkar and   
             Ivan Stojmenovi\'c   An optimal parallel circle-cover
                                  algorithm  . . . . . . . . . . . . . . . 3--6
                   Neil Gunther   Path integral methods for computer
                                  performance analysis . . . . . . . . . . 7--13
       Ji\vrí Matou\vsek   On-line computation of convolutions  . . 15--16
                   A. P. Sistla   On verifying that a concurrent program
                                  satisfies a nondeterministic
                                  specification  . . . . . . . . . . . . . 17--23
                    Kazuo Iwano   An improvement of Goldberg, Plotkin and
                                  Vaidya's maximal node-disjoint paths
                                  algorithm  . . . . . . . . . . . . . . . 25--27
                 Joachim Biskup   Boyce-Codd normal form and object normal
                                  forms  . . . . . . . . . . . . . . . . . 29--33
                 Torben Hagerup   Hybridsort revisited and parallelized    35--39
              Andreas Blass and   
                  Yuri Gurevich   On Matijasevitch's nontraditional
                                  approach to search problems  . . . . . . 41--45
                 Errol L. Lloyd   A fast algorithm for finding
                                  interlocking sets  . . . . . . . . . . . 47--50

Information Processing Letters
Volume 32, Number 2, July 24, 1989

             Hwang Kyu Choi and   
                  Myunghwan Kim   Hybrid join: an improved sort-based join
                                  algorithm  . . . . . . . . . . . . . . . 51--56
             Laurence Boxer and   
                    Russ Miller   A parallel circle-cover minimization
                                  algorithm  . . . . . . . . . . . . . . . 57--60
         Maw-Sheng S. Chern and   
                 G. H. Chen and   
                   Pangfeng Liu   An LC branch-and-bound algorithm for the
                                  module assignment problem  . . . . . . . 61--71
              Young Joo Kim and   
                  Gil Chang Kim   Coordinator: a modification to the
                                  monitor concept  . . . . . . . . . . . . 73--80
          Dror G. Feitelson and   
                  Larry Rudolph   Implementation of a wait-free
                                  synchronization primitive that solves
                                  $n$-process consensus  . . . . . . . . . 81--83
                  D. A. Wolfram   Forward checking and intelligent
                                  backtracking . . . . . . . . . . . . . . 85--87
                 Y. C. Chen and   
                  Z. C. Yeh and   
                     G. H. Chen   Using fewer processors to reduce time
                                  complexities of semigroup computations   89--93

Information Processing Letters
Volume 32, Number 3, August 24, 1989

              Chi Sung Laih and   
               Jau Yien Lee and   
                      Lein Harn   A new threshold scheme and its
                                  application in designing the conference
                                  key distribution cryptosystem  . . . . . 95--99
                    Adam Janiak   Minimization of resource consumption
                                  under a given deadline in the
                                  two-processor flow-shop scheduling
                                  problem  . . . . . . . . . . . . . . . . 101--112
              Shing-Tsaan Huang   Termination detection by using
                                  distributed snapshots  . . . . . . . . . 113--119
                  Martin Kochol   Efficient monotone circuits for
                                  threshold functions  . . . . . . . . . . 121--122
               Steven S. Skiena   Reconstructing graphs from cut-set sizes 123--127
                   A. Goscinski   A synchronization algorithm for
                                  processes with dynamic priorities in
                                  computer networks with node failures . . 129--136
         Stephen Richardson and   
            Mahadevan Ganapathi   Interprocedural analysis vs. procedure
                                  integration  . . . . . . . . . . . . . . 137--142
                  Paul Cull and   
              James L. Holloway   Computing Fibonacci numbers quickly  . . 143--149
                   G. Sagar and   
              Anil K. Sarje and   
                 Kamal U. Ahmed   On module assignment in two-processor
                                  distributed systems: A modified
                                  algorithm  . . . . . . . . . . . . . . . 151--153
               Joseph M. Morris   Well-founded induction and the
                                  invariance theorem for loops . . . . . . 155--158

Information Processing Letters
Volume 32, Number 4, September 1, 1989

         Mikhail J. Atallah and   
                  Danny Z. Chen   An optimal parallel algorithm for the
                                  minimum circle-cover problem . . . . . . 159--165
             Giri N. Narasimhan   A note on the Hamiltonian circuit
                                  problem on directed path graphs  . . . . 167--170
              Marshall Bern and   
                 Paul Plassmann   The Steiner problem with edge lengths
                                  $1$ and $2$  . . . . . . . . . . . . . . 171--176
      Gérard Ligozat and   
     Hél\`ene Bestougeff   On relations between intervals . . . . . 177--182
            Mohan B. Sharma and   
       Sitharama S. Iyengar and   
           Narasimha K. Mandyam   An efficient distributed
                                  depth-first-search algorithm . . . . . . 183--186
                   Micha Sharir   A note on the Papadimitriou-Silverberg
                                  algorithm for planning optimal
                                  piecewise-linear motion of a ladder  . . 187--190
                 Andrzej Lingas   Vorono\uì diagrams with barriers and the
                                  shortest diagonal problem  . . . . . . . 191--198
              John A. Ellis and   
              Manrique Mata and   
              Gary MacGillivray   A linear time algorithm for longest $(s,
                                  t)$-paths in weighted outerplanar graphs 199--204
    Ömer E\ugecio\uglu and   
               Bahman Kalantari   Approximating the diameter of a set of
                                  points in the Euclidean space  . . . . . 205--211
       Ravinderpal Singh Sandhu   The demand operation in the schematic
                                  protection model . . . . . . . . . . . . 213--219

Information Processing Letters
Volume 32, Number 5, September 22, 1989

                Jan van den Bos   PROCOL: A protocol-constrained
                                  concurrent object-oriented language  . . 221--227
                        R. Kemp   A one-to-one correspondence between two
                                  classes of ordered trees . . . . . . . . 229--234
                 Nissim Francez   Cooperating proofs for distributed
                                  programs with multiparty interactions    235--242
                 H. Everett and   
                       A. Gupta   Acyclic directed hypercubes may have
                                  exponential diameter . . . . . . . . . . 243--245
           Grant A. Cheston and   
                 Art Farley and   
           S. T. Hedetniemi and   
           Andrzej Proskurowski   Centering a spanning tree of a
                                  biconnected graph  . . . . . . . . . . . 247--250
    David A. Mix Barrington and   
                  James Corbett   On the relative complexity of some
                                  languages in ${\rm NC}^1$  . . . . . . . 251--256
                A. Clouatre and   
               N. Laliberte and   
                  T. H. Merrett   A general implementation of relational
                                  recursion with speedup techniques for
                                  programmers  . . . . . . . . . . . . . . 257--262
              George H. Roberts   Another note on recursive ascent . . . . 263--266
                 Gerd Baron and   
              Friedrich Urbanek   Factorial languages with quadratically
                                  upper bounded growth functions and
                                  nonlinearly upper bounded subword
                                  complexities . . . . . . . . . . . . . . 267--269
             Erkki Mäkinen   On the subtree isomorphism problem for
                                  ordered trees  . . . . . . . . . . . . . 271--273
          P. P. Chakrabarti and   
                   S. Ghose and   
                  A. Pandey and   
                S. C. de Sarkar   Increasing search efficiency using
                                  multiple heuristics  . . . . . . . . . . 275--275

Information Processing Letters
Volume 32, Number 6, October 3, 1989

                Shuji Shiraishi   A parallel algorithm for the maximum
                                  $2$-chain edge packing problem . . . . . 277--279
                Serge Abiteboul   Boundedness is undecidable for Datalog
                                  programs with a single recursive rule    281--287
                    Henk Alblas   Optimal incremental simple multi-pass
                                  attribute evaluation . . . . . . . . . . 289--295
            Manfred Padberg and   
                Antonio Sassano   The complexity of matching with bonds    297--300
    Robert L. Drysdale, III and   
             Jerzy W. Jaromczyk   A note on lower bounds for the maximum
                                  area and maximum perimeter $k$-gon
                                  problems . . . . . . . . . . . . . . . . 301--303
              A. M. Gibbons and   
                  Y. N. Srikant   A class of problems efficiently solvable
                                  on mesh-connected computers including
                                  dynamic expression evaluation  . . . . . 305--311
           Robert Demolombe and   
           Arantza Illarramendi   Heuristics for syntactical optimization
                                  of relational queries  . . . . . . . . . 313--316
            Serge Abiteboul and   
               Marc Gyssens and   
                 Dirk van Gucht   An alternative way to represent the
                                  cogroup of a relation in the context of
                                  nested databases . . . . . . . . . . . . 317--324
               Yoshihito Toyama   Fast Knuth--Bendix completion with a
                                  term rewriting system compiler . . . . . 325--328
                 Boris S. Veroy   Corrigenda: ``Average complexity of
                                  divide-and-conquer algorithms'' [Inform.
                                  Process. Lett. \bf 29 (1988), no. 6,
                                  319--326; MR 89m:68068]  . . . . . . . . 329--329
                 Boris S. Veroy   Corrigenda: ``Optimal search algorithm
                                  for a minimum of a discrete periodic
                                  bimodal function'' [Inform. Process.
                                  Lett. \bf 29 (1988), no. 5, 233--239; MR
                                  90b:90099] . . . . . . . . . . . . . . . 329--329


Information Processing Letters
Volume 33, Number 1, October 27, 1989

         Z. Fülöp and   
       S. Vágvölgyi   Top-down tree transducers with
                                  deterministic top-down look-ahead  . . . 3--5
                  S. J. Wan and   
                  S. K. M. Wong   An adaptive algorithm for finding a
                                  covering hypersphere . . . . . . . . . . 7--10
                     De-Lei Lee   On access and alignment of data in a
                                  parallel processor . . . . . . . . . . . 11--14
      Mila E. Majster-Cederbaum   The contraction property is sufficient
                                  to guarantee the uniqueness of fixed
                                  points of endofunctors in a category of
                                  complete metric spaces . . . . . . . . . 15--19
                  Jayadev Misra   A simple proof of a simple consensus
                                  algorithm  . . . . . . . . . . . . . . . 21--24
                Gadi Taubenfeld   Leader election in the presence of $n-1$
                                  initial failures . . . . . . . . . . . . 25--28
           A. Srinivasa Rao and   
                C. Pandu Rangan   Linear algorithm for domatic number
                                  problem on interval graphs . . . . . . . 29--33
           Bhaskar Dasgupta and   
            C. E. Veni Madhavan   An approximate algorithm for the minimal
                                  vertex nested polygon problem  . . . . . 35--44
                   Kam-Fai Wong   Comments on ``A comparison of
                                  concatenated and superimposed code word
                                  surrogate files for very large
                                  data/knowledge bases'' . . . . . . . . . 45--52
                  Michel Raynal   Prime numbers as a tool to design
                                  distributed algorithms . . . . . . . . . 53--58

Information Processing Letters
Volume 33, Number 2, November 10, 1989

                    D. Avis and   
               J. M. Robert and   
                      R. Wenger   Lower bounds for line stabbing . . . . . 59--62
               Christian Buchta   On the average number of maxima in a set
                                  of vectors . . . . . . . . . . . . . . . 63--65
            Kuo Liang Chung and   
              Wen Chin Chen and   
                Ferng-Ching Lin   Fast computation of periodic continued
                                  fractions  . . . . . . . . . . . . . . . 67--72
           Andrzej Szepietowski   Some remarks on the alternating
                                  hierarchy and closure under complement
                                  for sublogarithmic space . . . . . . . . 73--78
             Winfried Thome and   
               Reinhard Wilhelm   Simulating circular attribute grammars
                                  through attribute reevaluation . . . . . 79--81
          Martin Dietzfelbinger   The speed of copying on one-tape
                                  off-line Turing machines . . . . . . . . 83--89
     Alejandro A. Schäffer   Optimal node ranking of trees in linear
                                  time . . . . . . . . . . . . . . . . . . 91--96
               Stefano Ceri and   
              Georg Gottlob and   
              Letizia Tanca and   
                 Gio Wiederhold   Magic semi-joins . . . . . . . . . . . . 97--107
           Andrzej Szepietowski   Some notes on strong and weak $\log \log
                                  n$ space complexity  . . . . . . . . . . 109--112

Information Processing Letters
Volume 33, Number 3, November 30, 1989

                  R. Grossi and   
                      F. Luccio   Simple and efficient string matching
                                  with $k$ mismatches  . . . . . . . . . . 113--120
              Takayoshi Shoudai   The lexicographically first topological
                                  order problem is NLOG-complete . . . . . 121--124
             Lanfranco Lopriore   Software-controlled cache coherence
                                  protocol for multicache systems  . . . . 125--130
             E. Robert McCurley   Auxiliary variables in partial
                                  correctness programming logics . . . . . 131--133
               Selim G. Akl and   
                David Gries and   
        Ivan Stojmenovíc   An optimal parallel algorithm for
                                  generating combinations  . . . . . . . . 135--139
             Ronald V. Book and   
                  Shou Wen Tang   A note on sparse sets and the
                                  polynomial-time hierarchy  . . . . . . . 141--143
                Ravi B. Boppana   The average-case parallel complexity of
                                  sorting  . . . . . . . . . . . . . . . . 145--146
           A. Srinivasa Rao and   
                C. Pandu Rangan   Optimal parallel algorithms on
                                  circular-arc graphs  . . . . . . . . . . 147--156
               Bruce Parker and   
                   Ian Parberry   Constructing sorting networks from
                                  $k$-sorters  . . . . . . . . . . . . . . 157--162
          Rudolf Berghammer and   
       Günther Schmidt and   
                    Hans Zierer   Symmetric quotients and domain
                                  constructions  . . . . . . . . . . . . . 163--168

Information Processing Letters
Volume 33, Number 4, December 21, 1989

               John Hershberger   Finding the upper envelope of $n$ line
                                  segments in ${O}(n \log n)$ time . . . . 169--174
                  D. T. Lee and   
                F. P. Preparata   Parallel batched planar point location
                                  on the CCC . . . . . . . . . . . . . . . 175--179
             Torben Hagerup and   
             Christine Rüb   Optimal Merging and Sorting on the EREW
                                  PRAM . . . . . . . . . . . . . . . . . . 181--185
       Christos Levcopoulos and   
                  Ola Petersson   A note on adaptive parallel sorting  . . 187--191
                 Egon Wanke and   
                Manfred Wiegers   Undecidability of the bandwidth problem
                                  on linear graph languages  . . . . . . . 193--197
        José D. P. Rolim   On the polynomial IO-complexity  . . . . 199--204
        Jayaramaiah Boreddy and   
                R. N. Mukherjee   An algorithm to find polygon similarity  205--206
                 Richard Zippel   An explicit separation of relativised
                                  random polynomial time and relativised
                                  deterministic polynomial time  . . . . . 207--212
                    J. Zerovnik   A randomised heuristical algorithm for
                                  estimating the chromatic number of a
                                  graph  . . . . . . . . . . . . . . . . . 213--219


Information Processing Letters
Volume 34, Number 5, May 7, 1990

                    P. E. Dunne   Comment on Kochol's paper ``Efficient
                                  monotone circuits for threshold
                                  functions'' [Inform. Process. Lett. \bf
                                  32(3), 24 August 1989, pp. 121--122] . . 221--222


Information Processing Letters
Volume 35, Number 6, September 15, 1990

      A. J. M. Van Gasteren and   
                         G. Tel   Comments on ``On the proof of a
                                  distributed algorithm'': always-true is
                                  not invariant [Inform. Process. Lett.
                                  \bf 25(3), 29 May 1987, pp. 145--147]    277--279


Information Processing Letters
Volume 38, Number 4, May 31, 1991

                    Rolf Floren   A note on: ``A faster approximation
                                  algorithm for the Steiner problem in
                                  graphs'' [Inform. Process. Lett. \bf 27
                                  (1988), no. 3, 125--128; MR 89d:68031]
                                  by K. Mehlhorn . . . . . . . . . . . . . 177--178


Information Processing Letters
Volume 40, Number 5, December 13, 1991

            Jimmi S. Pettersson   Letter to the Editor: Comments on
                                  ``Always-true is not invariant'':
                                  Assertional reasoning about invariance
                                  [Inform. Process. Lett. \bf 35(6), 15
                                  September 1990, pp. 277--279]  . . . . . 231--233
                 Roberto Grossi   Further comments on the subtree
                                  isomorphism for ordered trees: ``On the
                                  subtree isomorphism problem for ordered
                                  trees'' [Inform. Process. Lett. \bf 32
                                  (1989), no. 5, 271--273; MR 90k:68139]
                                  by E. Mäkinen . . . . . . . . . . . . . . 255--256


Information Processing Letters
Volume 43, Number 5, October 5, 1992

          R. Satyanarayanan and   
            D. R. Muthukrishnan   A note on Raymond's tree based algorithm
                                  for distributed mutual exclusion . . . . 249--255


Information Processing Letters
Volume 47, Number 3, September 14, 1993

             George Steiner and   
                  Scott Yeomans   A note on: ``Scheduling unit-time tasks
                                  with integer release times and
                                  deadlines'' [Inform. Process. Lett. \bf
                                  16 (1983), no. 4, 171--173; MR
                                  84m:68030] by G. Frederickson  . . . . . 165--166