Table of contents for issues of Theoretical Computer Science

Last update: Sat Feb 8 17:15:09 MST 2014                Valid HTML 3.2!

Volume 70, Number 1, January 15, 1990
Volume 70, Number 2, January 26, 1990
Volume 70, Number 3, February 15, 1990
Volume 71, Number 1, March 13, 1990
Volume 71, Number 2, March 30, 1990
Volume 71, Number 3, April 10, 1990
Volume 72, Number 1, April 25, 1990
Volume 72, Number 2-3, May 23, 1990
Volume 73, Number 1, June 08, 1990
Volume 73, Number 2, June 22, 1990
Volume 73, Number 3, July 22, 1990
Volume 74, Number 1, July 30, 1990
Volume 74, Number 2, August 21, 1990
Volume 74, Number 3, August 28, 1990
Volume 75, Number 1-2, September 25, 1990
Volume 75, Number 3, October 01, 1990
Volume 76, Number 1, October 31, 1990
Volume 76, Number 2-3, November 21, 1990
Volume 77, Number 1-2, December 07, 1990
Volume 77, Number 3, December 15, 1990
Volume 78, Number 1, January 21, 1991
Volume 78, Number 2, January 31, 1991
Volume 79, Number 1, February 21, 1991
Volume 79, Number 2, February 27, 1991
Volume 80, Number 1, March 21, 1991
Volume 80, Number 2, March 29, 1991
Volume 81, Number 1, April 22, 1991
Volume 81, Number 2, April 30, 1991
Volume 82, Number 1, May 22, 1991
Volume 82, Number 2, May 31, 1991
Volume 83, Number 1, June 21, 1991
Volume 83, Number 2, June 28, 1991
Volume 84, Number 1, July 22, 1991
Volume 84, Number 2, July 29, 1991
Volume 85, Number 1, August 05, 1991
Volume 85, Number 2, August 12, 1991
Volume 86, Number 1, August 19, 1991
Volume 86, Number 2, September 02, 1991
Volume 87, Number 1, September 16, 1991
Volume 87, Number 2, September 23, 1991
Volume 88, Number 1, September 30, 1991
Volume 88, Number 2, October 07, 1991
Volume 89, Number 1, October 21, 1991
Volume 89, Number 2, October 28, 1991
Volume 90, Number 1, November 11, 1991
Volume 90, Number 2, November 25, 1991
Volume 91, Number 1, December 09, 1991
Volume 91, Number 2, December 23, 1991
Volume 92, Number 1, January 06, 1992
Volume 92, Number 2, January 20, 1992
Volume 93, Number 1, February 03, 1992
Volume 93, Number 2, February 17, 1992
Volume 94, Number 1, March 02, 1992
Volume 94, Number 2, March 09, 1992
Volume 95, Number 1, March 23, 1992
Volume 95, Number 2, March 30, 1992
Volume 96, Number 1, April 06, 1992
Volume 96, Number 2, April 13, 1992
Volume 97, Number 1, April 20, 1992
Volume 97, Number 2, April 27, 1992
Volume 98, Number 1, May 11, 1992
Volume 98, Number 2, May 18, 1992
Volume 99, Number 1, June 01, 1992
Volume 99, Number 2, June 08, 1992
Volume 100, Number 1, June 22, 1992
Volume 100, Number 2, June 29, 1992
Volume 101, Number 1, July 13, 1992
Volume 101, Number 2, July 20, 1992
Volume 102, Number 1, August 03, 1992
Volume 102, Number 2, August 10, 1992
Volume 103, Number 1, August 24, 1992
Volume 103, Number 2, September 14, 1992
Volume 104, Number 1, October 05, 1992
Volume 104, Number 2, October 12, 1992
Volume 105, Number 1, October 26, 1992
Volume 105, Number 2, November 09, 1992
Volume 106, Number 1, November 30, 1992
Volume 106, Number 2, December 14, 1992
Volume 107, Number 1, January 04, 1993
Volume 107, Number 2, January 18, 1993
Volume 108, Number 1, February 01, 1993
Volume 108, Number 2, February 15, 1993
Volume 109, Number 1-2, March 01, 1993
Volume 109, Number 1--2, March 01, 1993
Volume 110, Number 1, March 15, 1993
Volume 110, Number 2, March 29, 1993
Volume 111, Number 1--2, April 12, 1993
Volume 112, Number 1, April 26, 1993
Volume 112, Number 2, May 10, 1993
Volume 113, Number 1, May 24, 1993
Volume 113, Number 2, June 07, 1993
Volume 114, Number 1, June 14, 1993
Volume 114, Number 2, June 21, 1993
Volume 115, Number 1, July 05, 1993
Volume 115, Number 2, July 19, 1993
Volume 116, Number 1, August 02, 1993
Volume 116, Number 2, August 16, 1993
Volume 117, Number 1--2, August 30, 1993
Volume 118, Number 1, September 13, 1993
Volume 118, Number 2, September 27, 1993
Volume 119, Number 1, October 11, 1993
Volume 119, Number 2, October 25, 1993
Volume 120, Number 1, November 08, 1993
Volume 120, Number 2, November 22, 1993
Volume 121, Number 1--2, December 06, 1993
Volume 122, Number 1--2, January 03, 1994
Volume 123, Number 1, January 17, 1994
Volume 123, Number 2, January 31, 1994
Volume 124, Number 1, February 14, 1994
Volume 124, Number 2, February 28, 1994
Volume 125, Number 1, March 14, 1994
Volume 125, Number 2, March 28, 1994
Volume 126, Number 1, April 11, 1994
Volume 126, Number 2, April 25, 1994
Volume 127, Number 1, May 09, 1994
Volume 127, Number 2, May 23, 1994
Volume 128, Number 1--2, June 06, 1994
Volume 129, Number 1, June 20, 1994
Volume 129, Number 2, July 04, 1994
Volume 130, Number 1, August 01, 1994
Volume 130, Number 2, 1994
Volume 131, Number 1, August 29, 1994
Volume 131, Number 2, September 12, 1994
Volume 132, Number 1--2, September 26, 1994
Volume 133, Number 1, October 11, 1994
Volume 133, Number 2, October 24, 1994
Volume 134, Number 1, November 07, 1994
Volume 134, Number 2, November 21, 1994
Volume 135, Number 1, December 05, 1994
Volume 135, Number 2, December 12, 1994
Volume 136, Number 1, December 19, 1994
Volume 136, Number 2, December 29, 1994
Volume 141, Number 1--2, April 17, 1995
Volume 182, Number 1--2, August 15, 1997
Volume 206, Number 1--2, October 06, 1998
Volume 234, Number 1--2, March 6, 2000


Theoretical Computer Science
Volume 70, Number 1, January 15, 1990

                   E. G. Wagner   Algebras, polynomials and programs . . . 3--34
           E. S. Bainbridge and   
                P. J. Freyd and   
                 A. Scedrov and   
                    P. J. Scott   Functorial polymorphism  . . . . . . . . 35--64
                        M. Barr   Fixed points in Cartesian closed
                                  categories . . . . . . . . . . . . . . . 65--72
                    S. L. Bloom   A note on guarded theories . . . . . . . 73--83
                    P. S. Mulry   Categorical fixed point semantics  . . . 85--97
              H. R. Nielson and   
                     F. Nielson   Functional completeness of the mixed
                                  $\lambda$-calculus and combinatory logic 99--126
                     A. Pasztor   Recursive programs and denotational
                                  semantics in absolute logics of programs 127--150
                   C. Bottinger   On Scott's thesis for domains of
                                  information and well-quasi-orderings . . 151--158
                       C. Wells   A generalization of the concept of
                                  sketch . . . . . . . . . . . . . . . . . 159--178

Theoretical Computer Science
Volume 70, Number 2, January 26, 1990

                  J. Tiuryn and   
                   D. B. Benson   Fixed points in free process algebras.
                                  II . . . . . . . . . . . . . . . . . . . 179--192
                   G. Longo and   
                       E. Moggi   A category-theoretic characterization of
                                  functional completeness  . . . . . . . . 193--211
                 G. Senizergues   A characterisation of deterministic
                                  context-free languages by means of
                                  right-congruences  . . . . . . . . . . . 213--232
                        A. Jung   Cartesian closed categories of algebraic
                                  CPOs . . . . . . . . . . . . . . . . . . 233--250
                 G. Gambosi and   
                J. Nesetril and   
                      M. Talamo   On locally presented posets  . . . . . . 251--260
                    A. Terlutte   Cyclic rational transductions and
                                  polynomials of rational functions  . . . 261--271

Theoretical Computer Science
Volume 70, Number 3, February 15, 1990

             A. Ehrenfeucht and   
                   G. Rozenberg   Theory of $2$-structures. I. Clans,
                                  basic subclasses, and morphisms  . . . . 277--303
             A. Ehrenfeucht and   
                   G. Rozenberg   Theory of $2$-structures. II.
                                  Representation through labeled tree
                                  families . . . . . . . . . . . . . . . . 305--342
             A. Ehrenfeucht and   
                   G. Rozenberg   Primitivity is hereditary for
                                  $2$-structures . . . . . . . . . . . . . 343--358


Theoretical Computer Science
Volume 71, Number 1, March 13, 1990

                A. Aggarwal and   
              A. K. Chandra and   
                        M. Snir   Communication complexity of PRAMs  . . . 3--28
                   K. Culik, II   New techniques for proving the
                                  decidability of equivalence problems . . 29--45
                      J. Gruska   Synthesis, structure and power of
                                  systolic computations  . . . . . . . . . 47--77
                   J. Hartmanis   New developments in structural
                                  complexity theory  . . . . . . . . . . . 79--93
              C. P. Kruskal and   
                 L. Rudolph and   
                        M. Snir   A complexity theory of efficient
                                  parallel algorithms  . . . . . . . . . . 95--132
              P. S. Thiagarajan   Some behavioural aspects of net theory   133--153
                 W. P. Weijland   Semantics for logic programs without
                                  occur check  . . . . . . . . . . . . . . 155--174

Theoretical Computer Science
Volume 71, Number 2, March 30, 1990

                      Anonymous   INFORMATIKA 88. 2nd French-Soviet
                                  Workshop on Methods of Compilation and
                                  Program Construction . . . . . . . . . . ??
            J.-P. Arcangeli and   
                      C. Pomian   Principles of plasma pattern and
                                  alternative structure compilation  . . . 177--191
                     M. Billaud   Simple operational and denotational
                                  semantics for Prolog with cut  . . . . . 193--208
                M. A. Bulyonkov   Mixed computation and compilation: new
                                  approaches to old problems . . . . . . . 209--226
                    D. Galmiche   Constructive system for automatic
                                  program synthesis  . . . . . . . . . . . 227--239
                      J. Penjam   Computational and attribute models of
                                  formal languages . . . . . . . . . . . . 241--264
                V. K. Sabelfeld   An algorithm deciding functional
                                  equivalence in a new class of program
                                  schemes  . . . . . . . . . . . . . . . . 265--279

Theoretical Computer Science
Volume 71, Number 3, April 10, 1990

                 G. Senizergues   Some decision problems about controlled
                                  rewriting systems  . . . . . . . . . . . 281--346
                   H. Ehrig and   
         F. Parisi-Presicce and   
                   P. Boehm and   
               C. Rieckhoff and   
             C. Dimitrovici and   
                M. Grosse-Rhode   Combining data type and recursive
                                  process specifications using projection
                                  algebras . . . . . . . . . . . . . . . . 347--380
                  S. Dulucq and   
           D. Gouyou-Beauchamps   On the factors of the Sturmian sequences 381--400
                 A. Gibbons and   
                      W. Rytter   Optimally edge-colouring outerplanar
                                  graphs is in NC  . . . . . . . . . . . . 401--411
                    E. G. Manes   A transformational characterization of
                                  if-then-else . . . . . . . . . . . . . . 413--417
                 M. Chrobak and   
                T. Szymacha and   
                    A. Krawczyk   A data structure useful for finding
                                  Hamiltonian cycles . . . . . . . . . . . 419--424
                   K. Skandalis   Nonrecursiveness of the operations on
                                  real numbers . . . . . . . . . . . . . . 425--429


Theoretical Computer Science
Volume 72, Number 1, April 25, 1990

                 J. Sakarovitch   Foreword . . . . . . . . . . . . . . . . 1
                      L. Budach   Topological invariants of classification
                                  problems . . . . . . . . . . . . . . . . 3--26
                  K. Hashiguchi   Improved limitedness theorems on finite
                                  automata with distance functions . . . . 27--38
                   A. Carpi and   
                     A. de Luca   Non-repetitive words relative to a
                                  rewriting system . . . . . . . . . . . . 39--53
                     A. Restivo   Codes and local constraints  . . . . . . 55--64
                       I. Simon   Factorization forests of finite height   65--94

Theoretical Computer Science
Volume 72, Number 2-3, May 23, 1990

                      Anonymous   CAAP '88 --- 13th Colloque sur les
                                  Arbres en Alg\`ebre et en Programmation.
                                  (French) [Colloquium on Trees in Algebra
                                  and Programming] . . . . . . . . . . . . ??
                 M. Dauchet and   
                     J. L. Remy   Editorial  . . . . . . . . . . . . . . . 95
                G. Ausiello and   
                   U. Nanni and   
                 G. F. Italiano   Dynamic maintenance of directed
                                  hypergraphs  . . . . . . . . . . . . . . 97--117
                     E. Engeler   Combinatory differential fields  . . . . 119--131
                     R. Echahed   On completeness of narrowing strategies  133--146
                 J. Francon and   
       B. Randrianarimanana and   
                      R. Schott   Analysis of dynamic algorithms in
                                  Knuth's model  . . . . . . . . . . . . . 147--167
                 I. Gnaedig and   
                C. Kirchner and   
                    H. Kirchner   Equational completion in order-sorted
                                  algebras . . . . . . . . . . . . . . . . 169--202
                R. Gorrieri and   
               S. Marchetti and   
                   U. Montanari   $A^2 CCS$: atomic actions for $CCS$  . . 203--223
                    R. Kennaway   Implementing term rewrite languages in
                                  Dactl  . . . . . . . . . . . . . . . . . 225--249
                   R. Klein and   
                        D. Wood   A tight upper bound for the path length
                                  of AVL trees . . . . . . . . . . . . . . 251--264
                   K. G. Larsen   Proof systems for satisfiability in
                                  Hennessy--Milner Logic with recursion    265--288


Theoretical Computer Science
Volume 73, Number 1, June 08, 1990

                G. Jacopini and   
                   G. Sontacchi   Reversible parallel computation: an
                                  evolving space-model . . . . . . . . . . 1--46
                      F. Kroger   On the interpretability of arithmetic in
                                  temporal logic . . . . . . . . . . . . . 47--60
                     C. Lavault   Exact average message complexity values
                                  for distributed election on
                                  bidirectional rings of processors  . . . 61--79
                  S. Varricchio   Factorizations of free monoids and
                                  unavoidable regularities . . . . . . . . 81--89
                  M. Jerrum and   
                    A. Sinclair   Fast uniform generation of regular
                                  graphs . . . . . . . . . . . . . . . . . 91--100
                   H. Huwig and   
                      A. Poigne   A note on inconsistencies caused by
                                  fixpoints in a Cartesian closed category 101--112

Theoretical Computer Science
Volume 73, Number 2, June 22, 1990

                   H. Ganzinger   Foreword . . . . . . . . . . . . . . . . 119
                       A. Aiken   A theory of compaction-based
                                  parallelization  . . . . . . . . . . . . 121--154
            You-Chin C. Fuh and   
                      P. Mishra   Type inference with subtypes . . . . . . 155--175
                   R. Giegerich   Code selection by inversion of
                                  order-sorted derivors  . . . . . . . . . 177--211
                     S. Horwitz   Adding relational query facilities to
                                  software development environments  . . . 213--230
                      P. Wadler   Deforestation: transforming programs to
                                  eliminate trees  . . . . . . . . . . . . 231--248

Theoretical Computer Science
Volume 73, Number 3, July 22, 1990

                      R. Beigel   Bi-immunity results for cheatable sets   249--263
                   Jian-er Chen   The difference between one tape and two
                                  tapes: with respect to reversal
                                  complexity . . . . . . . . . . . . . . . 265--278
                J. Hoffmann and   
                     M. G. Main   Results on NLC grammars with one-letter
                                  terminal alphabets . . . . . . . . . . . 279--294
                  Changwook Kim   Complexity and decidability for
                                  restricted classes of picture languages  295--311
                   J. M. Robson   Strong time bounds: non-computable
                                  bounds and a hierarchy theorem . . . . . 313--317
             A. A. Bertossi and   
                  F. Luccio and   
                    E. Lodi and   
                       L. Pagli   String matching with weighted errors . . 319--328
                        T. Head   The set of strings mapped into a
                                  submonoid by iterates of a morphism  . . 329--333
                     W. Schmitt   Hopf algebras and identities in free
                                  partially commutative monoids  . . . . . 335--340


Theoretical Computer Science
Volume 74, Number 1, July 30, 1990

                     V. Diekert   Word problems over traces which are
                                  solvable in linear time  . . . . . . . . 3--18
                 D. Fussell and   
                  R. Thurimella   Successive approximation in parallel
                                  graph algorithms . . . . . . . . . . . . 19--35
        A. Gavilanes-Franco and   
              F. Lucio-Carrasco   A first order logic for partial
                                  functions  . . . . . . . . . . . . . . . 37--69
                      P. Jancar   Decidability of a temporal logic problem
                                  for Petri nets . . . . . . . . . . . . . 71--93
            F. P. Preparata and   
                    R. Tamassia   Dynamic planar point location with
                                  optimal query time . . . . . . . . . . . 95--114
                A. Szepietowski   If deterministic and nondeterministic
                                  space complexities are equal for $\log
                                  \log n$, then they are also equal for
                                  $\log n$ . . . . . . . . . . . . . . . . 115--119

Theoretical Computer Science
Volume 74, Number 2, August 21, 1990

                      P. Gastin   An asynchronous model for distributed
                                  systems  . . . . . . . . . . . . . . . . 121--162
                  F. Gecseg and   
                   H. Jurgensen   Automata represented by products of
                                  soliton automata . . . . . . . . . . . . 163--181
               B. J. Oommen and   
               E. R. Hansen and   
                    J. I. Munro   Deterministic optimal and expedient
                                  move-to-rear list organizing strategies  183--197
                    F. Okulicka   On priority in COSY  . . . . . . . . . . 199--216
               J. Hartmanis and   
              L. A. Hemachandra   Robust machine saccept easy sets . . . . 217--225
                       M. Bezem   Completeness of resolution revisited . . 227--237
                      H. Huttel   SnS can be modally characterized . . . . 239--248
                      M. Kummer   An easy priority-free proof of a theorem
                                  of Friedberg . . . . . . . . . . . . . . 249--251

Theoretical Computer Science
Volume 74, Number 3, August 28, 1990

            Jingzhong Zhang and   
                    Lu Yang and   
                        M. Deng   The parallel numerical method of
                                  mechanical theorem proving . . . . . . . 253--271
                   R. Casas and   
    M.-I. Fernandez-Camacho and   
                 J.-M. Steyaert   Algebraic simplification in computer
                                  algebra: an analysis of bottom-up
                                  algorithms . . . . . . . . . . . . . . . 273--298
                         Xin He   An efficient algorithm for edge coloring
                                  planar graphs with Delta colors  . . . . 299--312
                   L. Babai and   
                  P. Pudlak and   
                    V. Rodl and   
                   E. Szemeredi   Lower bounds to the complexity of
                                  symmetry Boolean functions . . . . . . . 313--323
                   U. Hertrampf   Relations among mod-classes  . . . . . . 325--328
                   J.-F. Romeuf   A polynomial algorithm for solving
                                  systems of two linear Diophantine
                                  equations  . . . . . . . . . . . . . . . 329--340
                     M. Anselmo   On zigzag codes and their decidability   341--354
                   J. Szymanski   On the complexity of algorithms on
                                  recursive trees  . . . . . . . . . . . . 355--361


Theoretical Computer Science
Volume 75, Number 1-2, September 25, 1990

                      Anonymous   International Conference on Fifth
                                  Generation Computer Systems 1988 . . . . ??
                      R. Milner   Interpreting one concurrent calculus in
                                  another  . . . . . . . . . . . . . . . . 3--13
            J. W. de Bakker and   
                      J. N. Kok   Comparative metric semantics for
                                  Concurrent Prolog  . . . . . . . . . . . 15--43
                M. Falaschi and   
                        G. Levi   Finite failures and partial computations
                                  in concurrent logic languages  . . . . . 45--66
                    M. Murakami   A declarative semantics of flat guarded
                                  Horn clauses for programs with perpetual
                                  processes  . . . . . . . . . . . . . . . 67--83
                  S. Holldobler   Conditional equational theories and
                                  complete sets of transformations . . . . 85--110
              N. Dershowitz and   
                       M. Okada   A rationale for conditional equational
                                  programming  . . . . . . . . . . . . . . 111--138
                T. Kawamura and   
                    T. Kanamori   Preservation of stronger equivalence in
                                  unfold/fold logic program transformation 139--156
                    P. Devienne   Weighted graphs: a tool for studying the
                                  halting problem and time complexity in
                                  term rewriting systems and logic
                                  programming  . . . . . . . . . . . . . . 157--215

Theoretical Computer Science
Volume 75, Number 3, October 01, 1990

                  P. Degano and   
               R. De Nicola and   
                   U. Montanari   A partial ordering semantics for CCS . . 223--262
                    S. Katz and   
                       D. Peled   Interleaving set temporal logic  . . . . 263--287
                  M. Droste and   
                       R. Gobel   Non-deterministic information systems
                                  and their domains  . . . . . . . . . . . 289--309
                   U. Blass and   
                 A. S. Fraenkel   The Sprague-Grundy function for
                                  Wythoff's game . . . . . . . . . . . . . 311--333
                E. Allender and   
                      C. Wilson   Downward translations of equality  . . . 335--346
                      J. Du and   
             J. Y.-T. Leung and   
                    G. H. Young   Minimizing mean flow time with release
                                  time constraint  . . . . . . . . . . . . 347--355
                T. Lengauer and   
                   K. W. Wagner   The binary network flow problem is
                                  logspace complete for P  . . . . . . . . 357--363


Theoretical Computer Science
Volume 76, Number 1, October 31, 1990

                   A. J. Bonner   Hypothetical datalog: complexity and
                                  expressibility . . . . . . . . . . . . . 3--51
                       A. Ohori   Semantics of types for database objects  53--91
                 D. Karabeg and   
                       V. Vianu   Parallel update transactions . . . . . . 93--114
                   U. W. Lipeck   Transformation of dynamic integrity
                                  constraints into transaction
                                  specifications . . . . . . . . . . . . . 115--142
                Guozhu Dong and   
                    S. Ginsburg   On the decomposition of datalog program
                                  mappings . . . . . . . . . . . . . . . . 143--177

Theoretical Computer Science
Volume 76, Number 2-3, November 21, 1990

                  J. N. Kok and   
             J. J. M. M. Rutten   Contractions in comparing concurrency
                                  semantics  . . . . . . . . . . . . . . . 179--222
                  Y. Sakakibara   Learning context-free grammars from
                                  structural data in polynomial time . . . 223--242
                   E. Timmerman   The three subfamilies of rational
                                  omega-languages closed under
                                  omega-transduction . . . . . . . . . . . 243--250
                        P. Weil   Products of languages with counter . . . 251--260
                       S. Tirri   The congruence theory of closure
                                  properties of regular tree languages . . 261--271
              K. Hashiguchi and   
                         H. Yoo   Extended regular expressions of star
                                  degree at most two . . . . . . . . . . . 273--284
                       A. Petit   Distribution and synchronized automata   285--308
                    S. Yamasaki   Recursion equation sets computing logic
                                  programs . . . . . . . . . . . . . . . . 309--322
                       T. Jiang   On the complexity of $1$-tape ATMs and
                                  off-line $1$-tape ATMs running in
                                  constant reversals . . . . . . . . . . . 323--330
                 E. Gannett and   
              S. C. Kothari and   
                      H.-C. Yen   On optimal parallelization of sorting
                                  networks . . . . . . . . . . . . . . . . 331--341
                 R. Sarnath and   
                         Xin He   A P-Complete Graph Partition Problem . . 343--351


Theoretical Computer Science
Volume 77, Number 1-2, December 07, 1990

                      Anonymous   International Conference on Algebraic
                                  Methodology and Software Technology,
                                  AMAST  . . . . . . . . . . . . . . . . . ??
                         T. Rus   Editorial  . . . . . . . . . . . . . . . 1
                     L. Bradley   Abstract language design . . . . . . . . 5--26
                   H. Ehrig and   
                     W. Fey and   
                  H. Hansen and   
                    M. Lowe and   
                  D. Jacobs and   
             F. Parisi-Presicce   Compatibility problems in the
                                  development of algebraic module
                                  specifications . . . . . . . . . . . . . 27--71
                    S. Even and   
                  D. A. Schmidt   Category-sorted algebra-based action
                                  semantics  . . . . . . . . . . . . . . . 73--95
                 R. Janicki and   
                     T. Muldner   Transformations of sequential
                                  specifications into concurrent
                                  specifications by synchronization guards 97--129
                   V. Manca and   
                 A. Salibra and   
                      G. Scollo   Equational type logic  . . . . . . . . . 131--159
                     D. Pigozzi   Data types over multiple-valued logics   161--194
                   E. G. Wagner   An algebraically specified language for
                                  data directed design . . . . . . . . . . 195--219

Theoretical Computer Science
Volume 77, Number 3, December 15, 1990

                        S. Toda   Positive relativizations for log space
                                  computability  . . . . . . . . . . . . . 221--235
                 S. Bozapalidis   Effective constructions on formal series
                                  of trees . . . . . . . . . . . . . . . . 237--247
                C. H. Smith and   
              M. Velauthapillai   On the inference of approximate programs 249--266
                    Y. Kawahara   Pushout-complements and basic concepts
                                  of grammars in toposes . . . . . . . . . 267--289
                  P. Atzeni and   
                  E. P. F. Chan   Efficient and optimal query answering on
                                  independent schemes  . . . . . . . . . . 291--308
              W. F. Dowling and   
                       R. Kline   The fixed points of logic programs with
                                  Herbrand base $N$  . . . . . . . . . . . 309--319
                 H. M. A. Fahmy   Analysis of Petri nets by partitioning:
                                  splitting transitions  . . . . . . . . . 321--330
                   M. Elbaz and   
                  J.-C. Spehner   Construction of Voronoi diagrams in the
                                  plane by using maps  . . . . . . . . . . 331--343


Theoretical Computer Science
Volume 78, Number 1, January 21, 1991

                      Anonymous   Workshop on Deductive Database Theory    ??
                      N. Bidoit   Negation in rule-based database
                                  languages: a survey  . . . . . . . . . . 3--83
                  N. Bidoit and   
                  C. Froidevaux   Negation by default and unstratifiable
                                  logic programs . . . . . . . . . . . . . 85--112
                       V. Royer   The semantics of incomplete databases as
                                  an expression of preferences . . . . . . 113--136
               S. Abiteboul and   
                       E. Simon   Fundamental properties of deterministic
                                  and nondeterministic extensions of
                                  Datalog  . . . . . . . . . . . . . . . . 137--158
               S. Abiteboul and   
              P. Kanellakis and   
                      G. Grahne   On the representation and querying of
                                  sets of possible worlds  . . . . . . . . 159--187
             J. P. Delahaye and   
                      V. Thibau   Programming in three-valued logic  . . . 189--216
                   B. Courcelle   Recursive queries and context-free graph
                                  grammars . . . . . . . . . . . . . . . . 217--244
                   R. Demolombe   An efficient strategy for non-Horn
                                  deductive databases  . . . . . . . . . . 245--259

Theoretical Computer Science
Volume 78, Number 2, January 31, 1991

              J. Engelfriet and   
                      H. Vogler   Modular tree transducers . . . . . . . . 267--303
                      R. Downey   On computational complexity and honest
                                  polynomial degrees . . . . . . . . . . . 305--317
                       R. Konig   Graphs and free partially commutative
                                  monoids  . . . . . . . . . . . . . . . . 319--346
                   T. Harju and   
                   J. Karhumaki   The equivalence problem of multitape
                                  finite automata  . . . . . . . . . . . . 347--355
        D. A. M. Barrington and   
                     J. Corbett   A note on some languages in uniform
                                  ACC$^0$  . . . . . . . . . . . . . . . . 357--362
              R. A. Baeza-Yates   Searching subsequences . . . . . . . . . 363--376
                 G. Burosch and   
             J. Demetrovics and   
            G. O. H. Katona and   
                   Kleitman and   
                      D. J. and   
               A. A. Sapozhenko   On the number of databases and closure
                                  operations . . . . . . . . . . . . . . . 377--381


Theoretical Computer Science
Volume 79, Number 1, February 21, 1991

                     M. Anselmo   The zig-zag power series: a two-way
                                  version of the * operator  . . . . . . . 3--24
                 A. Bertoni and   
                 D. Bruschi and   
                    M. Goldwurm   Ranking and formal power series  . . . . 25--35
                P. Flajolet and   
                   B. Salvy and   
                  P. Zimmermann   Automatic average-case analysis of
                                  algorithms . . . . . . . . . . . . . . . 37--109
                        D. Krob   Some examples of formal series used in
                                  non-commutative algebra  . . . . . . . . 111--135
                       W. Kuich   Automata and languages generalized to
                                  omega-continuous semirings . . . . . . . 137--150
                  C. Hespel and   
                       G. Jacob   Approximation of nonlinear dynamic
                                  systems by rational series . . . . . . . 151--162
             V. Hoang Ngoc Minh   Evaluation transform . . . . . . . . . . 163--177
                  P. Leroux and   
                  X. G. Viennot   A combinatorial approach to nonlinear
                                  functional expansions: an introduction
                                  with an example  . . . . . . . . . . . . 179--193
                  N. E. Oussous   Computation, on Macsyma, of the Minimal
                                  Differential Representation of
                                  Noncommutative Polynomials . . . . . . . 195--207
                      M. Delest   Enumeration of Polyominoes Using Macsyma 209--226
                     G. Duchamp   Orthogonal projection onto the free Lie
                                  algebra  . . . . . . . . . . . . . . . . 227--239
                 P.-V. Koseleff   Word games in free Lie algebras: several
                                  bases and formulas . . . . . . . . . . . 241--256
                     F. Rotella   Shuffle product of generating series . . 257--261
                     J. Honkala   On algebraic generalized zeta functions
                                  of formal power series . . . . . . . . . 263--273

Theoretical Computer Science
Volume 79, Number 2, February 27, 1991

               F. W. Vaandrager   Determinism to (event structure
                                  isomorphism=step sequence equivalence)   275--294
                      M. Holden   Weak logic theory  . . . . . . . . . . . 295--321
                   A. Jaoua and   
                    A. Mili and   
                N. Boudriga and   
                  J. L. Durieux   Regularity of relations: a measure of
                                  uniformity . . . . . . . . . . . . . . . 323--339
                      A. Szalas   On strictly arithmetical completeness in
                                  logics of programs . . . . . . . . . . . 341--355
                   A. Stoughton   Interdefinability of parallel operations
                                  in PCF . . . . . . . . . . . . . . . . . 357--358
                        A. Jung   The dependent product construction in
                                  various categories of domains  . . . . . 359--363
                    G. Koletsos   Polymorphic lambda calculus: the
                                  Church--Rosser property  . . . . . . . . 365--371


Theoretical Computer Science
Volume 80, Number 1, March 21, 1991

                      W. Reisig   Petri nets and algebraic specifications  1--34
                  F. Gecseg and   
                   H. Jurgensen   On $\alpha_0$-$\nu_1$-products of
                                  automata . . . . . . . . . . . . . . . . 35--51
             S. Heilbrunner and   
                     L. Schmitz   An efficient recognizer for the Boolean
                                  closure of context-free languages  . . . 53--75
               R. R. Howell and   
               L. E. Rosier and   
                   Hsu-Chun Yen   Global and local views of state fairness 77--104
                  P. Powell and   
                       Viet Ngo   Complexity of optimal vector code
                                  generation . . . . . . . . . . . . . . . 105--115
                       G. Hofer   Experiments and stability in group
                                  automata . . . . . . . . . . . . . . . . 117--120

Theoretical Computer Science
Volume 80, Number 2, March 29, 1991

                 H. Andreka and   
                  I. Nemeti and   
                        I. Sain   On the strength of temporal proofs . . . 125--151
                   B. Courcelle   The monadic second-order logic of
                                  graphs. V. On closing the gap between
                                  definability and recognizability . . . . 153--202
          L. A. Hemachandra and   
                   A. Hoene and   
                 D. Siefkes and   
                       P. Young   On sets polynomially enumerable by
                                  iteration  . . . . . . . . . . . . . . . 203--225
                   S. Iwanowski   Testing approximate symmetry in the
                                  plane is NP-hard . . . . . . . . . . . . 227--262
                  E.-R. Olderog   Correctness of concurrent processes  . . 263--288
                  D. Ranjan and   
                   R. Chang and   
                   J. Hartmanis   Space bounded computations: review and
                                  new separation results . . . . . . . . . 289--302
                 B. Steffen and   
                       J. Knoop   Finite constants: characterizations of a
                                  new decidable set of constants . . . . . 303--318
                 D. Szczepanska   A Hoare-like verification system for a
                                  language with an exception handling
                                  mechanism  . . . . . . . . . . . . . . . 319--335
                  J. Wiedermann   On the computational efficiency of
                                  symmetric neural networks  . . . . . . . 337--345


Theoretical Computer Science
Volume 81, Number 1, April 22, 1991

                   Z. Fulop and   
                   S. Vagvolgyi   A complete classification of
                                  deterministic root-to-frontier tree
                                  transformation classes . . . . . . . . . 1--15
                      J.-M. Boe   The boxes (automata theory)  . . . . . . 17--34
               Shouwen Tang and   
                     R. V. Book   Polynomial-time reducibilities and
                                  `almost all' oracle sets . . . . . . . . 35--47
                      O. Dubois   Counting the number of solutions for
                                  instances of satisfiability  . . . . . . 49--64
                  O. Dubois and   
                     J. Carlier   Probabilistic approach to the
                                  satisfiability problem . . . . . . . . . 65--75
                     M. Piotrow   On the complexity of counting in the
                                  polynomial hierarchy . . . . . . . . . . 77--95
                    A. Amir and   
                   G. M. Landau   Fast parallel and serial
                                  multidimensional approximate array
                                  matching . . . . . . . . . . . . . . . . 97--115
                       F. Matus   Abstract functional dependency
                                  structures . . . . . . . . . . . . . . . 117--126
                     J. H. Lutz   An upward measure separation theorem . . 127--135
                       H. Leung   Limitedness theorem on finite automata
                                  with distance functions: an algebraic
                                  proof  . . . . . . . . . . . . . . . . . 137--145
                    R. Cori and   
                M. R. Formisano   On the number of partially Abelian
                                  square-free words on a three-letter
                                  alphabet . . . . . . . . . . . . . . . . 147--153
                   J. Hartmanis   One-way functions and the nonisomorphism
                                  of NP-complete sets  . . . . . . . . . . 155--163

Theoretical Computer Science
Volume 81, Number 2, April 30, 1991

                   D. Kapur and   
                  D. Musser and   
               P. Narendran and   
                    J. Stillman   Semi-unification . . . . . . . . . . . . 169--187
            S. N. Khadilkar and   
                      S. Biswas   Padding, commitment and
                                  self-reducibility  . . . . . . . . . . . 189--199
                 K. Pingali and   
                   K. Ekanadham   Accumulators: new logic variable
                                  abstractions for functional languages    201--221
      K. S. H. S. R. Bhatta and   
                     H. Karnick   A resolution rule for well-formed
                                  formulae . . . . . . . . . . . . . . . . 223--235
               H. L. Bodlaender   New lower bound techniques for
                                  distributed leader finding and other
                                  problems on rings of processors  . . . . 237--256
                    K. Lenz and   
                     I. Wegener   The conjunctive complexity of quadratic
                                  Boolean functions  . . . . . . . . . . . 257--268
                P. R. J. Asveld   Abstract grammars based on transductions 269--288
                      J. Dassow   On the connectedness of pictures in
                                  chain code picture languages . . . . . . 289--294
              To-Yat Cheung and   
                    Yunzhou Zhu   Recognizing different types of
                                  beta-cycles in a database scheme . . . . 295--304
            E. Csuhaj-Varju and   
                     J. Kelemen   On the power of cooperation: a regular
                                  representation of recursively enumerable
                                  languages  . . . . . . . . . . . . . . . 305--310
                  M. Chytil and   
              M. Crochemore and   
                  B. Monien and   
                      W. Rytter   On the parallel recognition of
                                  unambiguous context-free languages . . . 311--316
                 N. Megiddo and   
            C. H. Papadimitriou   On total functions, existence theorems
                                  and computational complexity . . . . . . 317--324


Theoretical Computer Science
Volume 82, Number 1, May 22, 1991

               K. Weihrauch and   
                      C. Kreitz   Type $2$ computational complexity of
                                  functions on Cantor's space  . . . . . . 1--18
                       B. Lando   Periodicity and ultimate periodicity of
                                  D0L systems  . . . . . . . . . . . . . . 19--33
                  J.-J. Hebrard   An algorithm for distinguishing
                                  efficiently bit-strings by their
                                  subsequences . . . . . . . . . . . . . . 35--49
                       K.-I. Ko   On adaptive versus nonadaptive bounded
                                  query machines . . . . . . . . . . . . . 51--69
                     F. Mignosi   On the number of factors of Sturmian
                                  words  . . . . . . . . . . . . . . . . . 71--84
                        M. Snir   Size-depth trade-offs for monotone
                                  arithmetic circuits  . . . . . . . . . . 85--93
              J. Engelfriet and   
                    G. Leih and   
                   G. Rozenberg   Nonterminal separation in graph grammars 95--111
          M. Dietzfelbinger and   
                   W. Maass and   
                   G. Schnitger   The complexity of matrix transposition
                                  on one-tape off-line Turing machines . . 113--129
                 K. Salomaa and   
                          S. Yu   Decidability of structural equivalence
                                  of E0L grammars  . . . . . . . . . . . . 131--139
                   J. M. Robson   An O(T log T) reduction from RAM
                                  computations to satisfiability . . . . . 141--149
                  C. Calude and   
                     G. Istrate   Determining and stationary sets for some
                                  classes of partial recursive functions   151--155
                   V. Palko and   
                  O. Sykora and   
                        I. Vrto   Area complexity of merging . . . . . . . 157--163
                J. M. I. M. Leo   A general context-free parsing algorithm
                                  running in linear time on every LR(k)
                                  grammar without using lookahead  . . . . 165--176

Theoretical Computer Science
Volume 82, Number 2, May 31, 1991

                    M. Bauderon   Infinite hypergraphs. I. Basic
                                  properties . . . . . . . . . . . . . . . 177--214
              G. M. Germano and   
                    S. Mazzanti   Closure functions and general iterates
                                  as reflectors  . . . . . . . . . . . . . 215--252
                   M. Abadi and   
                     L. Lamport   The existence of refinement mappings . . 253--284
            J. C. M. Baeten and   
                J. A. Bergtstra   Recursive process definitions with the
                                  state operator . . . . . . . . . . . . . 285--302
                A. Lukassen and   
                      G. Vossen   A formal framework for independence with
                                  respect to transactions in the universal
                                  relation model . . . . . . . . . . . . . 303--327
                      W. Szwast   On Horn spectra  . . . . . . . . . . . . 329--339
               R. R. Howell and   
               L. E. Rosier and   
                   Hsu-Chun Yen   A taxonomy of fairness and temporal
                                  logic problems for Petri nets  . . . . . 341--372
                   F. Denis and   
                 J.-P. Delahaye   Is there an axiomatic semantics for
                                  standard pure Prolog?  . . . . . . . . . 373--388
                   P.-L. Curien   An abstract framework for environment
                                  machines . . . . . . . . . . . . . . . . 389--402
                 E. Badouel and   
                   P. Darondeau   On guarded recursion . . . . . . . . . . 403--408
                     R. Hoofman   Weakly expressive models for Hoare logic 409--418


Theoretical Computer Science
Volume 83, Number 1, June 21, 1991

           V. Breazu-Tannen and   
                     J. Gallier   Polymorphic rewriting conserves
                                  algebraic strong normalization . . . . . 3--28
                     F. Cardone   Recursive types for Fun  . . . . . . . . 29--56
                      L. Colson   About primitive recursive algorithms . . 57--69
              N. Dershowitz and   
                  S. Kaplan and   
                 D. A. Plaisted   Rewrite, rewrite, rewrite, rewrite,
                                  rewrite  . . . . . . . . . . . . . . . . 71--96
                   Z. Manna and   
                      A. Pnueli   Completing the temporal picture (logic)  97--130
             F. Parisi-Presicce   Foundations of rule-based design of
                                  modular systems  . . . . . . . . . . . . 131--155
                     G. Winskel   A note on model checking the modal
                                  $\nu$-calculus . . . . . . . . . . . . . 157--167

Theoretical Computer Science
Volume 83, Number 2, June 28, 1991

                   H. Luchkardt   New formally undecidable propositions:
                                  non-trivial lower bounds on proof
                                  complexity and related theorems  . . . . 169--188
                       D. Mauro   Derived linear systems of context-free
                                  grammars . . . . . . . . . . . . . . . . 189--203
           M. J. M. de Boer and   
             A. Lindenmayer and   
                        Z. Tuza   A periodic division pattern that cannot
                                  be generated by D0L systems  . . . . . . 205--218
                    S. Labhalla   Computational complexity of continuous
                                  fraction real number development . . . . 219--235
                    S. Seki and   
                     Y. Kobuchi   On standard locally catenative L schemes 237--248
                 E. Fachini and   
            A. M. Schettini and   
                   G. Resta and   
                   D. Sangiorgi   Nonacceptability criteria and closure
                                  properties for the class of languages
                                  accepted by binary systolic tree
                                  automata . . . . . . . . . . . . . . . . 249--260
                      G. Kuster   On the Hurwitz product of formal power
                                  series and automata  . . . . . . . . . . 261--273
                        Y. Azar   Parallel comparison merging of
                                  many-ordered lists . . . . . . . . . . . 275--285
                       S. Kundu   Minimal strings in a regular language
                                  with respect to a partial order on the
                                  alphabet . . . . . . . . . . . . . . . . 287--300
               J. Cohen-Chesnot   On the expressive power of temporal
                                  logic for infinite words . . . . . . . . 301--312
          L. A. Hemachandra and   
                    G. Wechsung   Kolmogorov characterizations of
                                  complexity classes . . . . . . . . . . . 313--322
                A. W. Mostowski   Hierarchies of weak automata and weak
                                  monadic formulas . . . . . . . . . . . . 323--335
                    O. Watanabe   On the $p$-isomorphism conjecture  . . . 337--343


Theoretical Computer Science
Volume 84, Number 1, July 22, 1991

               D. Beauquier and   
                      J.-E. Pin   Languages and scanners . . . . . . . . . 3--21
                G. Brassard and   
                 C. Crepeau and   
                        M. Yung   Constant-round perfect zero-knowledge
                                  computationally convincing protocols . . 23--52
                     V. Bruyere   Maximal codes with bounded deciphering
                                  delay  . . . . . . . . . . . . . . . . . 53--76
                B. Chazelle and   
            H. Edelsbrunner and   
               L. J. Guibas and   
                      M. Sharir   A singly exponential stratification
                                  scheme for real semi-algebraic varieties
                                  and its applications . . . . . . . . . . 77--105
                 G. Gambosi and   
                E. Nardelli and   
                      M. Talamo   A pointer-free data structure for
                                  merging heaps and min-max heaps  . . . . 107--126
        C. H. Papadimitriou and   
                  M. Yannakakis   Shortest paths without a map . . . . . . 127--150

Theoretical Computer Science
Volume 84, Number 2, July 29, 1991

                 M. Clausen and   
                   A. Dress and   
               J. Grabmeier and   
                   M. Karpinski   On zero-testing and interpolation of
                                  $k$-sparse multivariate polynomials over
                                  finite fields  . . . . . . . . . . . . . 151--164
                      A. Saoudi   Generalized automata on infinite trees
                                  and Muller-McNaughton's theorem  . . . . 165--177
                   S. Moran and   
                   Y. Wolfstahl   Optimal covering of cacti by
                                  vertex-disjoint paths  . . . . . . . . . 179--197
                      R. Beigel   Bounded queries to SAT and the Boolean
                                  hierarchy  . . . . . . . . . . . . . . . 199--223
                  B. Becker and   
                    U. Sparmann   Computations over finite monoids and
                                  their test complexity  . . . . . . . . . 225--250
                   C. P. Rupert   Which Kleene semigroups are finite?  . . 251--264
               H. A. Maurer and   
                 A. Salomaa and   
                        D. Wood   Bounded delay L codes  . . . . . . . . . 265--279
                  J. Dassow and   
                   H. Jurgensen   Deterministic soliton automata with a
                                  single exterior node . . . . . . . . . . 281--292
              W. A. Baldwin and   
                   G. O. Strawn   Multidimensional trees . . . . . . . . . 293--311


Theoretical Computer Science
Volume 85, Number 1, August 05, 1991

                       Jie Wang   On $p$-creative sets and $p$-completely
                                  creative sets  . . . . . . . . . . . . . 1--31
                J. Devolder and   
                    I. Litovsky   Finitely generated bi omega-languages    33--52
               O. H. Ibarra and   
                  Tao Jiang and   
                       Hui Wang   Parallel parsing on a one-way linear
                                  array of finite-state machines . . . . . 53--74
                     S. Lindell   An analysis of fixed-point queries on
                                  binary trees . . . . . . . . . . . . . . 75--95
                P. H. Rodenburg   Algebraic specifiability of data types
                                  with minimal computable parameters . . . 97--116
                 W. Szpankowski   A characterization of digital search
                                  trees from the successful search
                                  viewpoint  . . . . . . . . . . . . . . . 117--134
                  M. Kutylowski   Multihead one-way finite automata  . . . 135--153
                     I. Wegener   The complexity of the parity function in
                                  unbounded fan-in, unbounded depth
                                  circuits . . . . . . . . . . . . . . . . 155--170
               A. Cherubini and   
                 C. Citrini and   
             S. C. Reghizzi and   
                   D. Mandrioli   QRT FIFO automata, breadth-first
                                  grammars and their relations . . . . . . 171--203
                      P. Michel   An NP-complete language accepted in
                                  linear time by a one-tape Turing machine 205--212

Theoretical Computer Science
Volume 85, Number 2, August 12, 1991

                     M. Cialdea   Resolution for some first-order modal
                                  systems  . . . . . . . . . . . . . . . . 213--229
                  N. Doggaz and   
                    C. Kirchner   Completion for unification . . . . . . . 231--251
                      E. Sopena   Hypermap rewriting: a combinatorial
                                  approach . . . . . . . . . . . . . . . . 253--281
              R. D. Tennent and   
                    J. K. Tobin   Continuations in possible-world
                                  semantics  . . . . . . . . . . . . . . . 283--303
                      J. Kamper   Nonuniform proof systems: a new
                                  framework to describe nonuniform and
                                  probabilistic complexity classes . . . . 305--331
                        S. Goto   Proof normalization with nonstandard
                                  objects  . . . . . . . . . . . . . . . . 333--351
                      I. Bethke   Coherence spaces are untopological . . . 353--357


Theoretical Computer Science
Volume 86, Number 1, August 19, 1991

                      Anonymous   6th International Conference on Logic
                                  Programming (ICLP 89)  . . . . . . . . . ??
              F. S. de Boer and   
         J. J. M. M. Rutten and   
                  J. N. Kok and   
                 C. Palamidessi   Semantic models for concurrent logic
                                  languages  . . . . . . . . . . . . . . . 3--33
                  R. N. Bol and   
                  K. R. Apt and   
                     J. W. Klop   An analysis of loop checking mechanisms
                                  for logic programs . . . . . . . . . . . 35--79
                     L. Cavedon   Acyclic logic programs and the
                                  completeness of SLDNF-resolution . . . . 81--92
                    J. Lobo and   
               A. Rajasekar and   
                      J. Minker   Semantics of Horn and disjunctive logic
                                  programs . . . . . . . . . . . . . . . . 93--106
                        H. Seki   Unfold/fold transformation of stratified
                                  programs . . . . . . . . . . . . . . . . 107--139

Theoretical Computer Science
Volume 86, Number 2, September 02, 1991

                A. Averbuch and   
                   Z. Galil and   
                    S. Winograd   Classification of all the minimal
                                  bilinear algorithms for computing the
                                  coefficients of the product of two
                                  polynomials modulo a polynomial. II. The
                                  algebra $ G(u)(u^n) $  . . . . . . . . . 143--203
                  J.-C. Spehner   Merging in maps and in pavings . . . . . 205--232
                  K. Hashiguchi   Recognizable closures and submonoids of
                                  free partially commutative monoids . . . 233--241
                 M. Chrobak and   
                    D. Eppstein   Planar orientations with low out-degree
                                  and compaction of adjacency matrices . . 243--266
                  M. Krause and   
                  C. Meinel and   
                       S. Waack   Separating the eraser Turing machine
                                  classes $L_e$, $\hbox{NL}_e$,
                                  $\hbox{co-NL}_e$ and $P_e$ . . . . . . . 267--275
                    F. Gire and   
                       M. Nivat   Algebraic languages of biinfinite words  277--323
                 A. Bertoni and   
                M. Goldwurm and   
                    N. Sabadini   The complexity of computing the number
                                  of strings of given length in
                                  context-free languages . . . . . . . . . 325--342
                    C.-J. Seger   On the existence of speed-independent
                                  circuits . . . . . . . . . . . . . . . . 343--364
            R. M. Capocelli and   
                 L. Gargano and   
                     U. Vaccaro   Decoders with initial state invariance
                                  for multivalued encodings  . . . . . . . 365--375
              G. M. Benedek and   
                        A. Itai   Learnability with respect to fixed
                                  distributions  . . . . . . . . . . . . . 377--389


Theoretical Computer Science
Volume 87, Number 1, September 16, 1991

     V. Stoltenberg-Hanssen and   
                   J. V. Tucker   Algebraic and fixed point equations over
                                  inverse limits of algebras . . . . . . . 1--24
                   W. M. Farmer   Simple second-order languages for which
                                  unification is undecidable . . . . . . . 25--41
                   A. G. Heibig   Control machines: a new model of
                                  parallelism for compositional
                                  specifications and their effective
                                  compilation  . . . . . . . . . . . . . . 43--80
                H. Balsters and   
                 M. M. Fokkinga   Subtyping can have a simple semantics    81--96
                R. Fournier and   
                G. von Bochmann   The equivalence in the DCP model . . . . 97--114
                     L. Hallnas   Partial inductive definitions  . . . . . 115--142
                P. Gardiner and   
                      C. Morgan   Data refinement of predicate
                                  transformers . . . . . . . . . . . . . . 143--162
                      H. Zierer   Relation algebraic domain constructions  163--188
                        A. Wilm   Determinism and nondeterminism in PDL    189--202
                   M. Mezghiche   Weak completeness of type assignment in
                                  lambda-calculus models: a generalization
                                  of Hindley's result  . . . . . . . . . . 203--208
                  R. Milner and   
                       M. Tofte   Conduction in relational semantics . . . 209--220
                  W. McCune and   
                         L. Wos   The absence and the presence of fixed
                                  point combinators  . . . . . . . . . . . 221--228

Theoretical Computer Science
Volume 87, Number 2, September 23, 1991

                        Z. Esik   Results on homomorphic realization of
                                  automata by $\alpha_0$-products  . . . . 229--249
                    K. Diks and   
                      W. Rytter   On optimal parallel computations for
                                  sequences of brackets  . . . . . . . . . 251--262
                 M. Gyssens and   
                   D. Van Gucht   A comparison between algebraic query
                                  languages for flat and nested databases  263--286
            E. Csuhaj-Varju and   
                      J. Dassow   On bounded interpretations of grammar
                                  forms  . . . . . . . . . . . . . . . . . 287--313
                 A. de Luca and   
                  S. Varricchio   Finiteness and iteration conditions for
                                  semigroups . . . . . . . . . . . . . . . 315--327
                  N. Nirmal and   
                        R. Rama   Machine characterization of (E0L-E0L)
                                  array languages  . . . . . . . . . . . . 329--346
                      C. Calude   Relativized topological size of sets of
                                  partial recursive functions  . . . . . . 347--352


Theoretical Computer Science
Volume 88, Number 1, September 30, 1991

                 R. Gavalda and   
                 J. L. Balcazar   Strong and robustly strong
                                  polynomial-time reducibilities to sparse
                                  sets . . . . . . . . . . . . . . . . . . 1--14
               K. G. Larsen and   
                     B. Thomsen   Partial specifications and compositional
                                  verification . . . . . . . . . . . . . . 15--32
                      S. Miyano   $\Delta_2^P$-complete lexicographically
                                  first maximal subgraph problems  . . . . 33--57
              M. Crochemore and   
                      W. Rytter   Usefulness of the Karp-Miller-Rosenberg
                                  algorithm in parallel computations on
                                  strings and arrays . . . . . . . . . . . 59--82
                  M. Garzon and   
                   Y. Zalcstein   The complexity of Grigorchuk groups with
                                  application to cryptography  . . . . . . 83--98
                   Sang Cho and   
                  Dung T. Huynh   Finite-automaton aperiodicity is
                                  PSPACE-complete  . . . . . . . . . . . . 99--116
                 P. Shankar and   
                    B. S. Adiga   A graph-based regularity test for
                                  deterministic context-free languages . . 117--125
                     A. Salomaa   A deterministic algorithm for modular
                                  knapsack problems  . . . . . . . . . . . 127--138
                  J. Engelfriet   A regular characterization of graph
                                  languages definable in monadic
                                  second-order logic . . . . . . . . . . . 139--150
                  K. Aizawa and   
                    A. Nakamura   Graph grammars with path-controlled
                                  embedding  . . . . . . . . . . . . . . . 151--170
                S. Labhalla and   
                    H. Lombardi   Representation of real numbers by
                                  developments in whole bases and
                                  complexity . . . . . . . . . . . . . . . 171--182
                 S. Khuller and   
                 V. V. Vazirani   Planar graph coloring is not
                                  self-reducible, assuming P not=NP  . . . 183--189

Theoretical Computer Science
Volume 88, Number 2, October 07, 1991

                    H. Seki and   
               T. Matsumura and   
                   M. Fujii and   
                      T. Kasami   On multiple context-free grammars  . . . 191--229
                  U. Huckenbeck   A result about the power of geometric
                                  oracle machines  . . . . . . . . . . . . 231--251
                       K. Peeva   Equivalence, reduction and minimization
                                  of finite automata over semirings  . . . 269--285
                   K. Inoue and   
                     A. Ito and   
                    I. Takanami   A note on real-time one-way alternating
                                  multicounter machines  . . . . . . . . . 287--296
                  A. Bebjak and   
                 I. Stefanekova   Separation of deterministic,
                                  nondeterministic and alternating
                                  complexity classes . . . . . . . . . . . 297--311
                        W. Baur   On the algebraic complexity of rational
                                  iteration procedures . . . . . . . . . . 313--324
                   A. Weber and   
                       H. Seidl   On the degree of ambiguity of finite
                                  automata . . . . . . . . . . . . . . . . 325--349
                     H. Yoo and   
                  K. Hashiguchi   Extended automata-like regular
                                  expressions of star degree at most (2,
                                  1) . . . . . . . . . . . . . . . . . . . 351--363
                     P. Seebold   Fibonacci morphisms and Sturmian words   365--384


Theoretical Computer Science
Volume 89, Number 1, October 21, 1991

                   H. Ganzinger   Order-sorted completion: the many-sorted
                                  way  . . . . . . . . . . . . . . . . . . 3--32
                   A. Habel and   
             H.-J. Kreowski and   
                      W. Vogler   Decidable boundedness problems for sets
                                  of graphs generated by
                                  hyperedge-replacement  . . . . . . . . . 33--62
                       M. Hanus   Horn clause programs with polymorphic
                                  types: semantics and resolution  . . . . 63--106
                  R. Harper and   
                     R. Pollack   Type checking with universes . . . . . . 107--136
                F. Pfenning and   
                         P. Lee   Metacircularity in the polymorphic
                                  $\lambda$-calculus . . . . . . . . . . . 137--159
                C. Stirling and   
                      D. Walker   Local model checking in the modal
                                  mu-calculus  . . . . . . . . . . . . . . 161--177
              C. A. Vissers and   
                  G. Scollo and   
            M. van Sinderen and   
                    E. Brinksma   Specification styles in distributed
                                  systems design and verification  . . . . 179--206

Theoretical Computer Science
Volume 89, Number 2, October 28, 1991

                        D. Krob   Complete systems of B-rational
                                  identities . . . . . . . . . . . . . . . 207--343


Theoretical Computer Science
Volume 90, Number 1, November 11, 1991

                    D. E. Knuth   Theory and practice (computer science)   1--15
                 I. V. Pottosin   Analysis of program optimization
                                  possibilities and further development    17--36
                    V. Kasyanov   Transformational approach to program
                                  concretization . . . . . . . . . . . . . 37--46
                M. A. Bulyonkov   From partial evaluation to mixed
                                  computation  . . . . . . . . . . . . . . 47--60
                Y. Futamura and   
                    K. Nogi and   
                      A. Takano   Essence of generalized partial
                                  computation  . . . . . . . . . . . . . . 61--79
                    V. E. Itkin   An algebra of mixed computation  . . . . 81--93
                    N. D. Jones   Static semantics, types, and binding
                                  time analysis  . . . . . . . . . . . . . 95--118
                   W. M. Turski   Prescribing behaviours . . . . . . . . . 119--125
            J. W. de Bakker and   
             J. H. A. Warmerdam   Four domains for concurrency . . . . . . 127--149
           L. A. Cherkasova and   
                    V. E. Kotov   An algebra of concurrent
                                  nondeterministic processes . . . . . . . 151--170
            A. Mazurkiewicz and   
              A. Rabinovich and   
             B. A. Trakhtenbrot   Connectedness and synchronization  . . . 171--184
                       E. Tyugu   Higher order dataflow schemas  . . . . . 185--198
              J. M. Barzdin and   
                  G. J. Barzdin   Rapid construction of algebraic axioms
                                  from samples . . . . . . . . . . . . . . 199--208
                  A. Blikle and   
                A. Tarlecki and   
                      M. Thorup   On conservative extensions of syntax in
                                  system development . . . . . . . . . . . 209--233
                 C. A. R. Hoare   A theory for the derivation of
                                  combinational C-MOS circuit designs  . . 235--251
                N. N. Nepejvoda   A bridge between constructive logic and
                                  computer programming . . . . . . . . . . 253--270

Theoretical Computer Science
Volume 90, Number 2, November 25, 1991

                         T. Rus   Algebraic construction of compilers  . . 271--308
                     M. Tatsuta   Program synthesis using realizability    309--353
                       T. Saito   Dynamics of equivalence relations in
                                  automata networks  . . . . . . . . . . . 355--367
                      Y. Toyama   How to prove equivalence of term
                                  rewriting systems without induction  . . 369--390
                Guozhu Dong and   
                    S. Ginsburg   Localizable constraints for object
                                  histories  . . . . . . . . . . . . . . . 391--432
                   D. Vakarelov   Modal logics for knowledge
                                  representation systems . . . . . . . . . 433--456


Theoretical Computer Science
Volume 91, Number 1, December 09, 1991

              A. Srinivasan and   
                   C. P. Rangan   Efficient algorithms for the minimum
                                  weighted dominating clique problem on
                                  permutation graphs . . . . . . . . . . . 1--21
                 P. Buneman and   
                    A. Jung and   
                       A. Ohori   Using powerdomains to generalize
                                  relational databases . . . . . . . . . . 23--55
               K. Culik, II and   
                        S. Dube   An efficient solution of the firing mob
                                  problem  . . . . . . . . . . . . . . . . 57--69
                        M. Arfi   Polynomial operations and hierarchies of
                                  concatenation  . . . . . . . . . . . . . 71--84
                  K. Hashiguchi   Algorithms for determining relative
                                  inclusion star height and inclusion star
                                  height . . . . . . . . . . . . . . . . . 85--100
                   E. B. Kinber   On complete sets of samples for
                                  generalized regular expressions  . . . . 101--117
                       D. Moews   Sums of games born on Days 2 and 3 . . . 119--128

Theoretical Computer Science
Volume 91, Number 2, December 23, 1991

                 P. Kearney and   
                     J. Staples   An extensional fixed-point semantics for
                                  nondeterministic data flow . . . . . . . 129--179
       P. M. W. Knijnenburg and   
                 J. van Leeuwen   On models for propositional dynamic
                                  logic  . . . . . . . . . . . . . . . . . 181--203
                      W. Vogler   Executions: a new partial-order
                                  semantics of Petri nets  . . . . . . . . 205--238
                A. Tarlecki and   
             R. M. Burstall and   
                   J. A. Goguen   Some fundamental algebraic tools for the
                                  semantics of computation. 3. Indexed
                                  categories . . . . . . . . . . . . . . . 239--264
                   Wenhui Zhang   Cut elimination and automatic proof
                                  procedures . . . . . . . . . . . . . . . 265--284
                   B. Rozoy and   
              P. S. Thiagarajan   Event structures and trace monoids . . . 285--313


Theoretical Computer Science
Volume 92, Number 1, January 06, 1992

                      Anonymous   Combinatorial Pattern Matching School    ??
                  M. Crochemore   Foreword to the Special Issue on
                                  Selected Papers of the Combinatorial
                                  Pattern Matching School, Paris, July
                                  1990 . . . . . . . . . . . . . . . . . . 1
              A. Apostolico and   
                  S. Browne and   
                      C. Guerra   Fast linear-space computations of
                                  longest common subsequences  . . . . . . 3--17
          R. A. Baeza-Yates and   
                     M. Regnier   Average running time of the
                                  Boyer--Moore--Horspool algorithm . . . . 19--31
                  M. Crochemore   String-matching on ordered alphabets . . 33--47
                   Z. Galil and   
                        K. Park   Dynamic programming with convexity,
                                  concavity, and sparsity  . . . . . . . . 49--76
              K. Hashiguchi and   
                      K. Yamada   Two recognizable string-matching
                                  problems over free partially commutative
                                  monoids  . . . . . . . . . . . . . . . . 77--86
           C. S. Iliopoulos and   
                    W. F. Smyth   Optimal algorithms for computing the
                                  canonical form of a circular string  . . 87--105
                  J. Y. Kim and   
                J. Shawe-Taylor   An approximate string-matching algorithm 107--117
                      T. Lecroq   A variation on the Boyer--Moore
                                  algorithm  . . . . . . . . . . . . . . . 119--144
                  J. Neraud and   
                  M. Crochemore   A string matching interpretation of the
                                  equation $x^m y^n=z^p$ . . . . . . . . . 145--164
                    R. W. Quong   Fast average-case pattern matching by
                                  multiplexing sparse tables . . . . . . . 165--179
                       D. Revuz   Minimisation of acyclic deterministic
                                  automata in linear time  . . . . . . . . 181--189
                     E. Ukkonen   Approximate string-matching with
                                  $q$-grams and maximal matches  . . . . . 191--211
                    M. Zipstein   Data compression with factor automata    213--221

Theoretical Computer Science
Volume 92, Number 2, January 20, 1992

             A. Ehrenfeucht and   
                   G. Rozenberg   Angular $2$-structures . . . . . . . . . 227--248
                    M. Goldwurm   Probabilistic estimation of the number
                                  of prefixes of a trace . . . . . . . . . 249--268
                 U. Hebisch and   
                  H. J. Weinert   Generalized semigroup semirings which
                                  are zero-divisor-free or
                                  multiplicatively left-cancellative . . . 269--289
                   J. Bitar and   
                       E. Goles   Parallel chip firing games on graphs . . 291--300
                     J. H. Lutz   On independent random oracles  . . . . . 301--307
          L. A. Hemachandra and   
               R. S. Rubinstein   Separating complexity classes with tally
                                  oracles  . . . . . . . . . . . . . . . . 309--318
            H. Edelsbrunner and   
                  L. Guibas and   
                    J. Pach and   
                 R. Pollack and   
                     Seidel and   
                         R. and   
                      M. Sharir   Arrangements of curves in the
                                  plane-topology, combinatorics and
                                  algorithms . . . . . . . . . . . . . . . 319--336


Theoretical Computer Science
Volume 93, Number 1, February 03, 1992

               A. J. Kfoury and   
                  J. Tiuryn and   
                    P. Urzyczyn   On the expressive power of finitely
                                  typed and universally polymorphic
                                  recursive procedures . . . . . . . . . . 1--41
                   S. Vagvolgyi   Top-down tree transducers with two-way
                                  tree walking look-ahead  . . . . . . . . 43--74
                   G. E. Revesz   A list-oriented extension of the
                                  lambda-calculus satisfying the
                                  Church--Rosser theorem . . . . . . . . . 75--89
             P. G. Harrison and   
                H. Khoshnevisan   A new approach to recursion removal  . . 91--113
             V. S. Subrahmanian   Paraconsistent disjunctive deductive
                                  databases  . . . . . . . . . . . . . . . 115--141
                Guo-Qiang Zhang   Stable neighbourhoods  . . . . . . . . . 143--157
                      A. Goerdt   Unrestricted resolution versus
                                  N-resolution . . . . . . . . . . . . . . 159--167

Theoretical Computer Science
Volume 93, Number 2, February 17, 1992

                    P. Peladeau   Logically defined subsets of $N^k$ . . . 169--183
                K. Hiraishi and   
                    A. Ichikawa   On structural conditions for weak
                                  persistency and semilinearity of Petri
                                  nets . . . . . . . . . . . . . . . . . . 185--199
                G. Louchard and   
       B. Randrianarimanana and   
                      R. Schott   Dynamic algorithms in D. E. Knuth's
                                  model: a probabilistic analysis  . . . . 201--225
               P. Bonizzoni and   
                       G. Mauri   On automata on infinite trees  . . . . . 227--244
                Z. M. Kedem and   
                    K. V. Palem   Optimal parallel algorithms for forest
                                  and term matching  . . . . . . . . . . . 245--264
                        S. Toda   Restricted relativizations of
                                  probabilistic polynomial time  . . . . . 265--277
                     P. Ramanan   Testing the optimality of alphabetic
                                  trees  . . . . . . . . . . . . . . . . . 279--301
                   J. Boyar and   
                G. Frandsen and   
                  C. Sturtivant   An arithmetic model of computation
                                  equivalent to threshold circuits . . . . 303--319
                    P. Dehornoy   A criterion for proving noetherianity of
                                  a relation . . . . . . . . . . . . . . . 321--325
                      T. Herbst   On a kind of Fatou property of
                                  context-free groups  . . . . . . . . . . 327--331


Theoretical Computer Science
Volume 94, Number 1, March 02, 1992

                    U. Waldmann   Semantics of order-sorted specifications 1--35
                    F. Lamarche   Quantitative domains and infinitary
                                  algebras . . . . . . . . . . . . . . . . 37--62
              I. Filippenko and   
                   F. L. Morris   Domains for logic programming  . . . . . 63--69
                   V. Manca and   
                     A. Salibra   Soundness and completeness of the
                                  Birkhoff equational calculus for
                                  many-sorted algebras with possibly empty
                                  carrier sets . . . . . . . . . . . . . . 101--124
                       P. Caspi   Clocks in dataflow languages . . . . . . 125--140
                     M. Koutney   Adequacy-preserving transformations of
                                  COSY path programs . . . . . . . . . . . 141--158

Theoretical Computer Science
Volume 94, Number 2, March 09, 1992

                     C. Mauduit   Introduction . . . . . . . . . . . . . . 159
             J.-P. Allouche and   
                  P. Morton and   
                     J. Shallit   Pattern spectra, substring enumeration,
                                  and automatic sequences  . . . . . . . . 161--174
              L. Baratchart and   
                   M. Olivi and   
                   F. Wielonsky   On a rational approximation problem in
                                  the real Hardy space $H_2$ . . . . . . . 175--197
                    P. Dehornoy   Probl\`eme de mots dans les gerbes
                                  libres. (French) [Word problems in free
                                  groups]  . . . . . . . . . . . . . . . . 199--213
                    S. Ferenczi   Tiling the Morse sequence  . . . . . . . 215--221
                    Ch. Frougny   Syst\`emes de numération linéaires et
                                  theta-représentations. (French) [Linear
                                  numeration systems and
                                  theta-representation]  . . . . . . . . . 223--236
                    D. Galmiche   Program development in constructive type
                                  theory . . . . . . . . . . . . . . . . . 237--259
                       D. Gardy   Méthode de col et lois limités en analyse
                                  combinatoire. (French) [Bottleneck
                                  method and limit laws in combinational
                                  analysis]  . . . . . . . . . . . . . . . 261--280
                         B. Gil   Complete extension of general logic
                                  programs . . . . . . . . . . . . . . . . 281--294
                     G. Lachaud   Artin--Schreier curves, exponential
                                  sums, and coding theory  . . . . . . . . 295--310
                        D. Mery   The NU system as a development system
                                  for concurrent programs: delta NU  . . . 311--334
                  D. Perrin and   
                     M. Parigot   Recursive programming with proofs  . . . 335--356
                      D. Perrin   On positive matrices . . . . . . . . . . 357
                     A. Restivo   A note on renewal systems  . . . . . . . 367--371
              Zhi-Xiong Wen and   
                   Zhi-Ying Wen   Some studies on the $(p,q)$-type
                                  sequences  . . . . . . . . . . . . . . . 373--393


Theoretical Computer Science
Volume 95, Number 1, March 23, 1992

                   V. Vianu and   
                      G. Vossen   Conceptual level concurrency control of
                                  relational update transactions . . . . . 1--42
                L. Giordano and   
                A. Martelli and   
                       G. Rossi   Extending Horn clause logic with
                                  implication goals  . . . . . . . . . . . 43--74
                        I. Sain   Temporal logics need their clocks  . . . 75--95
                 S. Arikawa and   
               T. Shinohara and   
                    A. Yamamoto   Learning elementary formal systems . . . 97--113
                  G. Bellin and   
                     J. Ketonen   A decision procedure revisited: Notes on
                                  direct logic, linear logic and its
                                  implementation . . . . . . . . . . . . . 115--142
                  B. Jacobs and   
                I. Margaria and   
                      M. Zacchi   Filter models with polymorphic types . . 143--158
                   S. R. Schwer   Fine covers of a VAS language  . . . . . 159--168
                   J. Beauquier   Two distributed problems involving
                                  Byzantine processes  . . . . . . . . . . 169--185

Theoretical Computer Science
Volume 95, Number 2, March 30, 1992

            J. Moulin Ollagnier   Proof of Dejean's conjecture for
                                  alphabets with 5, 6, 7, 8, 9, 10 and 11
                                  letters  . . . . . . . . . . . . . . . . 187--205
                 P. Quinton and   
                      Y. Robert   Systolic convolution of arithmetic
                                  functions  . . . . . . . . . . . . . . . 207--229
                  Y. Rabani and   
                       Z. Galil   On the space complexity of some
                                  algorithms for sequence comparison . . . 231--244
                G. Ausiello and   
             G. F. Italiano and   
    A. Marchetti Spaccamela and   
                       U. Nanni   On-line computation of minimal and
                                  maximal length paths . . . . . . . . . . 245--261
                       S. Zhang   Polynomial-time algorithms for testing
                                  strong isomorphism and computing the
                                  automorphism group of R-strongly
                                  connected automata . . . . . . . . . . . 263--277
                      L. Pierre   Rational indexes of generators of the
                                  cone of context-free languages . . . . . 279--305
                     J. Spencer   Ulam's searching game with a fixed
                                  number of lies . . . . . . . . . . . . . 307--321
                  S. G. Akl and   
                 M. Cosnard and   
                 A. G. Ferreira   Data-movement-intensive problems: two
                                  folk theorems in parallel computation
                                  revisited  . . . . . . . . . . . . . . . 323--337
                 P. Shankar and   
                    B. S. Adiga   A graph-based regularity test for
                                  deterministic context-free languages . . 339--340


Theoretical Computer Science
Volume 96, Number 1, April 06, 1992

                      Anonymous   2nd Workshop on Concurrency and
                                  Compositionality . . . . . . . . . . . . ??
               R. De Nicola and   
                   U. Montanari   Preface  . . . . . . . . . . . . . . . . 1
                 M. Nielsen and   
               G. Rozenberg and   
              P. S. Thiagarajan   Elementary transition systems  . . . . . 3--33
                  M. Mukund and   
              P. S. Thiagarajan   A logical characterization of well
                                  branching event structures . . . . . . . 35--72
                    J. Meseguer   Conditional rewriting logic as a unified
                                  model of concurrency . . . . . . . . . . 73--155
               J. Bradfield and   
                    C. Stirling   Local model checking for infinite state
                                  spaces . . . . . . . . . . . . . . . . . 157--174
                    E. Best and   
                      M. Koutny   Petri net semantics of priority systems  175--215
                   G. Berry and   
                      G. Boudol   The chemical abstract machine  . . . . . 217--248
               E. Astesiano and   
                 A. Giovini and   
                      G. Reggio   Observational structures and their
                                  logics . . . . . . . . . . . . . . . . . 249--283

Theoretical Computer Science
Volume 96, Number 2, April 13, 1992

                 V. K. Garg and   
                 M. T. Ragunath   Concurrent regular expressions and their
                                  relationship to Petri nets . . . . . . . 285--304
                    D. T. Huynh   Nonuniform complexity and the randomness
                                  of certain complete languages  . . . . . 305--324
                     M. Ito and   
               H. Jurgensen and   
                 H. J. Shyr and   
                    G. Thierrin   Languages whose $n$-element subsets are
                                  codes  . . . . . . . . . . . . . . . . . 325--344
                       R. Barua   The Hausdorff-Kuratowski hierarchy of
                                  omega-regular languages and a hierarchy
                                  of Muller automata . . . . . . . . . . . 345--360
                 T. E. Plambeck   Daisies, Kayles, and the Sibert-Conway
                                  decomposition in misere octal games  . . 361--388
                 T. S. Ferguson   Mate with bishop and knight in
                                  Kriegspiel (mathematical games)  . . . . 389--403
                 G. Duchamp and   
                        D. Krob   On the partially commutative shuffle
                                  product  . . . . . . . . . . . . . . . . 405--410
                   A. Slobodova   Some properties of space-bounded
                                  synchronized alternating Turing machines
                                  with universal states only . . . . . . . 411--419


Theoretical Computer Science
Volume 97, Number 1, April 20, 1992

               J. Y. Girard and   
                 A. Scedrov and   
                    P. J. Scott   Bounded linear logic: a modular approach
                                  to polynomial-time computability . . . . 1--66
                   S. M. German   Semantics and reasoning with free
                                  procedures . . . . . . . . . . . . . . . 67--81
                 J. Perraud and   
                    O. Roux and   
                        M. Huou   Operational semantics of a kernel of the
                                  language ELECTRE . . . . . . . . . . . . 83--103
                  A. Monfroglio   Integer programs for logic constraint
                                  satisfaction . . . . . . . . . . . . . . 105--130
               P. Darondeau and   
                   D. Nolte and   
                  L. Priese and   
                      S. Yoccoz   Fairness, distances and degrees  . . . . 131--142
                   S. Baratella   A completeness result for allowed
                                  semi-strict programs with respect to
                                  well-behaved and allowed query clauses   143--156
                      T. Weibel   Extension of combinatory logic to a
                                  theory of combinatory representation . . 157--173
                       K. Doets   A slight strengthening of a theorem of
                                  Blair and Kunen  . . . . . . . . . . . . 175--181

Theoretical Computer Science
Volume 97, Number 2, April 27, 1992

                  M. W. Krentel   Generalizations of Opt P to the
                                  polynomial hierarchy . . . . . . . . . . 183--198
                O. Watanabe and   
                   Shouwen Tang   On polynomial-time Turing and many-one
                                  completeness in PSPACE . . . . . . . . . 199--215
                     H. Yoo and   
                  K. Hashiguchi   Extended regular expressions of
                                  arbitrary star degrees . . . . . . . . . 217--231
               D. E. Muller and   
                  A. Saoudi and   
                   P. E. Schupp   Alternating automata, the weak monadic
                                  theory of trees and its complexity . . . 233--244
                      G. Karner   Nivat's theorem for pushdown transducers 245--262
                R. A. Shore and   
                   T. A. Slaman   The $p$-$T$-degrees of the recursive
                                  sets: lattice embeddings, extensions of
                                  embeddings and the two-quantifier theory 263--284
               J. Hromkovic and   
               S. A. Lozkin and   
                A. I. Rybko and   
            A. A. Sapozenko and   
                N. A. Skalikova   Lower bounds on the area complexity of
                                  Boolean circuits . . . . . . . . . . . . 285--300
                 G. Guaiana and   
                 A. Restivo and   
                      S. Salemi   Star-free trace languages  . . . . . . . 301--311


Theoretical Computer Science
Volume 98, Number 1, May 11, 1992

                 G. Duchamp and   
                   G. Jacob and   
                        D. Krob   Second Workshop on Algebraic and
                                  Computer-Theoretic Aspects of Formal
                                  Power Series . . . . . . . . . . . . . . ??
                    C. Choffrut   Rational relations and rational series   5--13
                   J. Karhumaki   Multiplicities: A deterministic view of
                                  nondeterminism . . . . . . . . . . . . . 15--25
                      G. Karner   On transductions of formal power series
                                  over complete semirings  . . . . . . . . 27--39
                  S. Varricchio   Rational series with coefficients in a
                                  commutative ring . . . . . . . . . . . . 41--50
                 A. Bjorner and   
                  C. Reutenauer   Rationality of the Möbius function of
                                  subword order  . . . . . . . . . . . . . 53--63
               M. P. Delest and   
                    J. M. Fedou   Attribute grammars are useful for
                                  combinatorics  . . . . . . . . . . . . . 65--76
                     G. Cauchon   Séries de Malcev-Neumann sur le groupe
                                  libre et questions de rationalité.
                                  (French) [Malcev-Neumann series on the
                                  free group and questions on nationality] 79--97
                       F. Dumas   Skew power series rings with general
                                  commutation formula  . . . . . . . . . . 99--114
                    B. Mourrain   Computable identities in the algebra of
                                  formal matrices  . . . . . . . . . . . . 115--133
                        S. Diop   Differential-algebraic decision methods
                                  and some applications to system theory   137--161

Theoretical Computer Science
Volume 98, Number 2, May 18, 1992

             J.-P. Allouche and   
                     J. Shallit   The ring of $k$-regular sequences  . . . 163--197
                   S. R. Schwer   The context-freeness of the languages
                                  associated with vector addition systems
                                  is decidable . . . . . . . . . . . . . . 199--247
                 L. Santean and   
                        J. Kari   The impact of the number of cooperating
                                  grammars on the generative power . . . . 249--262
                   Hsu-Chun Yen   A multiparameter analysis of domino
                                  tiling with an application to concurrent
                                  systems  . . . . . . . . . . . . . . . . 263--287
                M. A. Palis and   
                   S. M. Shende   Upper bounds on recognition of a
                                  hierarchy of non-context-free languages  289--319
                Do Long Van and   
                 Phan Trung Huy   Varieties of finite monoids and
                                  Buchi-McNaughton theorem . . . . . . . . 321--337
                 M. Chrobak and   
                  L. L. Larmore   HARMONIC is $3$-competitive for two
                                  servers  . . . . . . . . . . . . . . . . 339--346
                  T. Amtoft and   
               J. Larsson Traff   Partial memoization for obtaining linear
                                  time behavior of a 2DPDA . . . . . . . . 347--356


Theoretical Computer Science
Volume 99, Number 1, June 01, 1992

            V.-E. Cazanescu and   
                 Gh. Stefanescu   A general result on abstract flowchart
                                  schemes with applications to the study
                                  of accessibility, reduction and
                                  minimization . . . . . . . . . . . . . . 1--63
                        J. Hein   Completions of perpetual logic programs  65--78
                  J. L. Lambert   A structure to decide reachability in
                                  Petri nets . . . . . . . . . . . . . . . 79--104
                W. H. Hesselink   Processes and formalisms for unbounded
                                  choice . . . . . . . . . . . . . . . . . 105--119
                  L. Priese and   
                       D. Nolte   Strong fairness and ultra metrics  . . . 121--140
                    P. S. Mulry   Monads and algebras in the semantics of
                                  partial data types . . . . . . . . . . . 141--155
             S. Rajasekaran and   
                     J. H. Reif   Nested annealing: a provable improvement
                                  to simulated annealing . . . . . . . . . 157--176

Theoretical Computer Science
Volume 99, Number 2, June 08, 1992

                 S. Bozapalidis   Alphabetic tree relations  . . . . . . . 177--211
                   J. Nummenmaa   Constructing compact rectilinear planar
                                  layouts using canonical representation
                                  of planar graphs . . . . . . . . . . . . 213--230
                      J. Neraud   On the rank of the subsets of a free
                                  monoid . . . . . . . . . . . . . . . . . 231--241
               O. H. Ibarra and   
                     N. Q. Tran   On space-bounded synchronized
                                  alternating Turing machines  . . . . . . 243--264
                       S. Zhang   Efficient simplicity testing of automata 265
             J. L. Balcazar and   
                    U. Schoning   Logarithmic advice classes . . . . . . . 279--290
                  S. Varricchio   On the decidability of the equivalence
                                  problem for partially commutative
                                  rational power series  . . . . . . . . . 291--299
               O. H. Ibarra and   
                  Tao Jiang and   
                       Hui Wang   A characterization of exponential-time
                                  languages by alternating context-free
                                  grammars . . . . . . . . . . . . . . . . 301--315
                    J. D. Fouks   Tseitin's formulas revisited . . . . . . 315
                       B. Mosse   Puissances de mots et reconnaissabilité
                                  des points fixes d'une substitution.
                                  (French) [Word power and recognizability
                                  of substitutional fixed points]  . . . . 327
                    C. T. Hoang   A parallel algorithm for minimum
                                  weighted colouring of triangulated
                                  graphs . . . . . . . . . . . . . . . . . 335--344


Theoretical Computer Science
Volume 100, Number 1, June 22, 1992

               J. L. Trahan and   
                 M. C. Loui and   
                V. Ramachandran   Multiplication, division, and shift
                                  instructions in parallel random access
                                  machines . . . . . . . . . . . . . . . . 1--44
                      A. Goerdt   Characterizing complexity classes by
                                  higher type primitive recursive
                                  definitions  . . . . . . . . . . . . . . 45--66
                 A. De Luca and   
                  S. Varricchio   On noncounting regular classes . . . . . 67--104
                   R. Holte and   
                  L. Rosier and   
              I. Tulchinsky and   
                      D. Varvel   Pinwheel scheduling with two distinct
                                  numbers  . . . . . . . . . . . . . . . . 105--135
               D. Benninger and   
                      J. Schmid   Effective subdirect decomposition: a
                                  case study . . . . . . . . . . . . . . . 137--156
                   R. Board and   
                        L. Pitt   On the necessity of Occam algorithms . . 157--184
                 N. Santoro and   
               J. B. Sidney and   
                   S. J. Sidney   A distributed selection algorithm and
                                  its expected communication complexity    185--204
                    S. Toda and   
                    O. Watanabe   Polynomial time $1$-Turing reductions
                                  from #PH to #P . . . . . . . . . . . . . 205--221
                   P. Erdos and   
                      D. F. Hsu   Distributed loop network with minimum
                                  transmission delay . . . . . . . . . . . 223--241
                   H. Prodinger   Hypothetical analyses: approximate
                                  counting in the style of Knuth, path
                                  length in the style of Flajolet  . . . . 243--251
                   P. Beame and   
                 E. Brisson and   
                      R. Ladner   The complexity of computing symmetric
                                  functions using threshold circuits . . . 253--265

Theoretical Computer Science
Volume 100, Number 2, June 29, 1992

                 L. S. Moss and   
                J. Meseguer and   
                   J. A. Goguen   Final algebras, cosemicomputable
                                  algebras and degrees of unsolvability    267--302
      M. Dezani-Ciancaglini and   
                  J. R. Hindley   Intersection types for combinatory logic 303--324
                      M. Bartha   Foundations of a theory of synchronous
                                  systems  . . . . . . . . . . . . . . . . 325--346
                        Ke Wang   On characterizing boundedness of
                                  database schemes with bounded
                                  dependencies . . . . . . . . . . . . . . 347--364
              R. J. R. Back and   
                  J. Von Wright   Combining angels, demons and miracles in
                                  program specifications . . . . . . . . . 365--383
                      K. Meinke   Universal algebra in higher types  . . . 385--417


Theoretical Computer Science
Volume 101, Number 1, July 13, 1992

                   E. Grandjean   Editorial  . . . . . . . . . . . . . . . 1
                   B. Courcelle   The monadic second-order logic of graphs
                                  VII: Graphs as relational structures . . 3--33
                      E. Gradel   Capturing complexity classes by
                                  fragments of second-order logic  . . . . 35--57
                 J. Mazoyer and   
                      N. Reimen   A linear speed-up theorem for cellular
                                  automata . . . . . . . . . . . . . . . . 59--98
                      P. Michel   A survey of space complexity . . . . . . 99--132
                    P. Peladeau   Formulas, regular languages and Boolean
                                  circuits . . . . . . . . . . . . . . . . 133--141
                M. de Rougemont   The functional dimension of inductive
                                  definitions  . . . . . . . . . . . . . . 143--158

Theoretical Computer Science
Volume 101, Number 2, July 20, 1992

              M. Z. Kwiatkowska   Editorial  . . . . . . . . . . . . . . . 159
                  Eike Best and   
            Jörg Desel and   
                 Javier Esparza   Traps characterize home states in free
                                  choice systems . . . . . . . . . . . . . 161--176
            Stephen Brookes and   
                      Shai Geva   Towards a theory of parallel algorithms
                                  on concrete data structures  . . . . . . 177--221
                 Bard Bloom and   
                Albert R. Meyer   Experimenting with process equivalence   223--237
              F. S. de Boer and   
                  J. N. Kok and   
             C. Palamidessi and   
             J. J. M. M. Rutten   From failure to success: comparing a
                                  denotational and a declarative semantics
                                  for Horn clause logic  . . . . . . . . . 239--263
             Jeremy Gunawardena   Causal automata  . . . . . . . . . . . . 265--288
            J. J. M. Hooman and   
                  S. Ramesh and   
                W. P. de Roever   A compositional axiomatization of
                                  Statecharts  . . . . . . . . . . . . . . 289--335
                Shmuel Katz and   
                    Doron Peled   Defining conditional independence using
                                  collapses  . . . . . . . . . . . . . . . 337--359


Theoretical Computer Science
Volume 102, Number 1, August 03, 1992

                     Klaus Grue   Map theory . . . . . . . . . . . . . . . 1--134
                   S. Van Bakel   Complete restrictions of the
                                  intersection type discipline . . . . . . 135--163
                   R. Devillers   Maximality preserving bisimulation . . . 165--183
                 J. Esparza and   
                       M. Silva   A polynomial-time algorithm to decide
                                  liveness of bounded free choice nets . . 185--205
                       K. Dosen   Nonmodal classical linear predicate
                                  logic is a fragment of intuitionistic
                                  linear logic . . . . . . . . . . . . . . 207--214

Theoretical Computer Science
Volume 102, Number 2, August 10, 1992

                     D. Bruschi   Strong separations of the polynomial
                                  hierarchy with oracles: constructive
                                  separations by immune and simple sets    215--252
                M. Skubiszewski   Binary periodic synchronizing sequences  253--281
                   P. Dagum and   
                        M. Luby   Approximating the permanent of graphs
                                  with large factors . . . . . . . . . . . 283--305
                 R. Mirwald and   
                  C. P. Schnorr   The multiplicative complexity of
                                  quadratic Boolean forms  . . . . . . . . 307--328
              Liam Halpenny and   
           Christopher J. Smyth   A classification of minimal
                                  standard-path $2\times2$ switching
                                  networks . . . . . . . . . . . . . . . . 329--354
                  L. Prasad and   
                  S. S. Iyengar   An asymptotic equality for the number of
                                  necklaces in a shuffle-exchange network  355--365


Theoretical Computer Science
Volume 103, Number 1, August 24, 1992

                C. Choffrut and   
                     Th Lengaur   Editorial  . . . . . . . . . . . . . . . 1
                  R. Beigel and   
                        J. Gill   Counting classes: thresholds, parity,
                                  mods, and fewness  . . . . . . . . . . . 3--23
                 Jin-Yi Cai and   
                  A. Condon and   
                   R. J. Lipton   On games of incomplete information . . . 25--38
                M. Clerbout and   
                        Y. Roos   Semicommutations and algebraic languages 39--49
               A. Corradini and   
                   U. Montanari   An algebraic semantics for structured
                                  transition systems and its applications
                                  to logic programs  . . . . . . . . . . . 51--106
                     G. Das and   
                      D. Joseph   Minimum vertex hulls for polyhedral
                                  domains  . . . . . . . . . . . . . . . . 107--135
                  J. L. Lambert   Sorting the sums $(x_i+y_j)$ in $O(n^2)$
                                  comparisons  . . . . . . . . . . . . . . 137--141
                      W. Thomas   Infinite trees and automaton-definable
                                  relations over omega-words . . . . . . . 143--159

Theoretical Computer Science
Volume 103, Number 2, September 14, 1992

                Michel Bauderon   Infinite hypergraphs II. Systems of
                                  recursive equations  . . . . . . . . . . 165--190
         Kiyoharu Hamaguchi and   
            Hiromi Hiraishi and   
                   Shuzo Yajima   $\infty$-Regular temporal logic and its
                                  model checking problem . . . . . . . . . 191--204
                    L. Palopoli   Testing logic programs for local
                                  stratification . . . . . . . . . . . . . 205--234
               M. Felleisen and   
                        R. Hieb   The revised report on the syntactic
                                  theories of sequential control and state 235--271
                M. Kurihara and   
                      A. Ohuchi   Modularity of simple termination of term
                                  rewriting systems with shared
                                  constructors . . . . . . . . . . . . . . 273--282
             Byeong Man Kim and   
                   Jung Wan Cho   A new subsumption method in the
                                  connection graph proof procedure . . . . 283--309
                   C. A. Gunter   The mixed powerdomain  . . . . . . . . . 311--334
      A. Maggiolo-Schettini and   
                   J. Winkowski   Towards an algebra for timed behaviours  335--363
                   W. Marek and   
             V. S. Subrahmanian   The relationship between stable,
                                  supported, default and autoepistemic
                                  semantics for general logic programs . . 365--386
               Harry G. Mairson   A simple proof of a theorem of Statman   387--394
               Thomas Streicher   Independence of the induction principle
                                  and the axiom of choice in the pure
                                  calculus of constructions  . . . . . . . 395--408
                    Max Dauchet   Simulation of Turing machines by a
                                  regular rewrite rule . . . . . . . . . . 409--420


Theoretical Computer Science
Volume 104, Number 1, October 05, 1992

                       A. Miola   Foreword . . . . . . . . . . . . . . . . 1
                  Roland N. Bol   Generalizing completeness results for
                                  loop checks in logic programming . . . . 3--28
      Jean-Pierre Jouannaud and   
           Claude Marché   Termination and completion modulo
                                  associativity, commutativity and
                                  identity . . . . . . . . . . . . . . . . 29--51
                 Rolf Hennicker   A semi-algorithm for algebraic
                                  implementation proofs  . . . . . . . . . 53--87
              C. Limongelli and   
                   M. Temperini   Abstract specification of structures and
                                  methods in symbolic mathematical
                                  computation  . . . . . . . . . . . . . . 89--107
                Mark E. Stickel   A Prolog technology theorem prover: a
                                  new exposition and implementation in
                                  Prolog . . . . . . . . . . . . . . . . . 109--128
                Carolyn Talcott   A theory for program and data type
                                  specification  . . . . . . . . . . . . . 129--159

Theoretical Computer Science
Volume 104, Number 2, October 12, 1992

               H. Straubing and   
                        P. Weil   On a conjecture concerning dot-depth two
                                  languages  . . . . . . . . . . . . . . . 161--183
              Changwook Kim and   
               I. H. Sudborough   On reversal-bounded picture languages    185--206
                      Y. Takada   Learning semilinear sets from examples
                                  and via queries  . . . . . . . . . . . . 207--233
                     D. J. Weir   A geometric hierarchy beyond
                                  context-free languages . . . . . . . . . 235--261
                D. P. Bovet and   
               P. Crescenzi and   
                   R. Silvestri   A uniform approach to define complexity
                                  classes  . . . . . . . . . . . . . . . . 263--283
                      K. Jansen   Processor optimization for flow graphs   285--298
         René Leermakers   Recursive ascent parsing: from Earley to
                                  Marcus . . . . . . . . . . . . . . . . . 299--312
              R. Leermakers and   
              L. Augusteijn and   
        F. E. J. Kruseman Aretz   A functional LR parser . . . . . . . . . 313--323


Theoretical Computer Science
Volume 105, Number 1, October 26, 1992

                 Phan Minh Dung   On the relations between stable and
                                  well-founded semantics of logic programs 7--25
       Kanchana Kanchanasut and   
               Peter J. Stuckey   Transforming normal logic programs to
                                  constraint logic programs  . . . . . . . 27--56
                   Taisuke Sato   Equivalence-preserving first-order
                                  unfold/fold transformation systems . . . 57--84
        Maurizio Gabbrielli and   
                   Giorgio Levi   Unfolding and fixpoint semantics of
                                  concurrent constraint logic programs . . 85--128
                Dieter Hofbauer   Termination proofs by multiset path
                                  orderings imply primitive recursive
                                  derivation lengths . . . . . . . . . . . 129--140
    Françoise Debart and   
          Patrice Enjalbert and   
               Madeleine Lescot   Multimodal logic programming using
                                  equational and order-sorted logic  . . . 141--166

Theoretical Computer Science
Volume 105, Number 2, November 09, 1992

                  Ian Mason and   
             Carolyn L. Talcott   Inferring the equivalence of functional
                                  programs that mutate data  . . . . . . . 167--215
           Joseph A. Goguen and   
           José Meseguer   Order sorted algebra I. Equational
                                  deduction for multiple inheritance,
                                  overloading, exceptions and partial
                                  operations . . . . . . . . . . . . . . . 217--273
                 Ming-Hua Zhang   Data types with errors and exceptions    275--299


Theoretical Computer Science
Volume 106, Number 1, November 30, 1992

                      A. Arnold   Preface  . . . . . . . . . . . . . . . . 1
                  G. Boudol and   
                   K. G. Larsen   Graphical versus logical specifications  3--20
                     J. Cai and   
                   R. Paige and   
                      R. Tarjan   More efficient bottom-up multi-pattern
                                  matching in trees  . . . . . . . . . . . 21--60
                      D. Caucal   On the regular structure of prefix
                                  rewriting  . . . . . . . . . . . . . . . 61--86
                    E. Kounalis   Testing for the ground (co-)reducibility
                                  property in term-rewriting systems . . . 87--117
             M. I. Schwartzbach   Interpretations of recursively defined
                                  types  . . . . . . . . . . . . . . . . . 119--134
                       H. Seidl   Single-valuedness of tree transducers is
                                  decidable in polynomial time . . . . . . 135--181

Theoretical Computer Science
Volume 106, Number 2, December 14, 1992

                    Ch. Frougny   Confluent linear numeration systems  . . 183--219
                      P. Michel   Complexity of logical theories involving
                                  coprimality  . . . . . . . . . . . . . . 221--241
                 M. El-Taha and   
                S. Stidham, Jr.   Deterministic analysis of queueing
                                  systems with heterogeneous servers . . . 243--264
                 M. W. Bern and   
              H. J. Karloff and   
                P. Raghavan and   
                    B. Schieber   Fast geometric approximation techniques
                                  and geometric embedding problems . . . . 265--281
                     R. Hausser   Complexity in left-associative grammar   283--308
         Hans L. Bodlaender and   
                 Dieter Kratsch   The complexity of coloring games on
                                  perfect graphs . . . . . . . . . . . . . 309--326
                   J. M. Robson   More languages of generalised star
                                  height $1$ . . . . . . . . . . . . . . . 327--335
               Roger Villemaire   The theory of $\lfloor N + V_k,
                                  V_l\rfloor$ is undecidable . . . . . . . 337--349
                    C. Damm and   
                     Ch. Meinel   Separating complexity classes related to
                                  Omega-decision trees . . . . . . . . . . 351--360
   Shou-Hsuan Stephen Huang and   
                Hongfei Liu and   
        Venkatraman Viswanathan   A sublinear parallel algorithm for some
                                  dynamic programming problems . . . . . . 361--371
          K. G. Subramanian and   
               R. Siromoney and   
                      L. Mathew   Lyndon trees . . . . . . . . . . . . . . 373--383
                 A. A. Razborov   On the distributional complexity of
                                  disjointness . . . . . . . . . . . . . . 385--390
                 Arne Andersson   Comments on ``On the balance property of
                                  Patricia tries: External path length
                                  viewpoint''  . . . . . . . . . . . . . . 391--393
        Peter Kirschenhofer and   
           Helmut Prodinger and   
           Wojciech Szpankowski   Probabilistic modeling of data
                                  structures on words: a reply to
                                  Professor Andersson's letter . . . . . . 395--400


Theoretical Computer Science
Volume 107, Number 1, January 04, 1993

                   A. L. Selman   Foreword . . . . . . . . . . . . . . . . 1
                 C. Alvarez and   
                      B. Jenner   A very hard log-space counting class . . 3--30
                  F. Bedard and   
                 F. Lemieux and   
                    P. McKenzie   Extensions to Barrington's M-program
                                  model  . . . . . . . . . . . . . . . . . 31--61
                  R. Heiman and   
                  I. Newman and   
                   A. Wigderson   On read-once threshold formulae and
                                  their randomized decision tree
                                  complexity . . . . . . . . . . . . . . . 63--76
                    K.-J. Lange   Unambiguity of circuits  . . . . . . . . 77--94
                 J. H. Lutz and   
                  W. J. Schmidt   Circuit size relative to pseudorandom
                                  oracles  . . . . . . . . . . . . . . . . 95--120
                 Y. Mansour and   
                   N. Nisan and   
                      P. Tiwari   The computational complexity of
                                  universal hashing  . . . . . . . . . . . 121--133
                       N. Nisan   On read-once vs. multiple access to
                                  randomness in logspace . . . . . . . . . 135--144
               A. Panconesi and   
                      D. Ranjan   Quantifiers and approximation  . . . . . 145--163

Theoretical Computer Science
Volume 107, Number 2, January 18, 1993

                    Bart Jacobs   Comprehension categories and the
                                  semantics of type dependency . . . . . . 169--207
               Marco Bellia and   
            M. Eugenia Occhiuto   $C$-expressions: a variable-free
                                  calculus for equational logic
                                  programming  . . . . . . . . . . . . . . 209--252
                Sachio Hirokawa   Principal types of BCK-lambda-terms  . . 253--276
           Agostino Cortesi and   
           Gilberto Filé   Graph properties for normal logic
                                  programs . . . . . . . . . . . . . . . . 277--303
            Michael G. Main and   
                 David L. Black   Semantic models for total correctness
                                  and fairness . . . . . . . . . . . . . . 305--332
          Vugranam Sreedhar and   
                   Kazem Taghva   Capturing strong reduction in director
                                  string calculus  . . . . . . . . . . . . 333--347
                   Gilles Dowek   The undecidability of pattern matching
                                  in calculi where primitive recursive
                                  functions are representable  . . . . . . 349--356
               Robin Milner and   
                   Faron Moller   Unique decomposition of processes  . . . 357--363


Theoretical Computer Science
Volume 108, Number 1, February 01, 1993

                      Anonymous   International Colloquium on Words,
                                  Languages and Combinatorics  . . . . . . ??
                         M. Ito   Foreword . . . . . . . . . . . . . . . . 1
                  Jorge Almeida   Locally commutative power semigroups and
                                  counting factors of words  . . . . . . . 3--16
      Sini\vsa Crvenkovi\'c and   
Rozália Sz. Madarász   On Kleene algebras . . . . . . . . . . . 17--24
                 Volker Diekert   Möbius functions and confluent
                                  semi-commutations  . . . . . . . . . . . 25--43
         Christiane Frougny and   
            Jacques Sakarovitch   Synchronized rational relations of
                                  finite and infinite words  . . . . . . . 45--82
                     Max Garzon   Cayley automata  . . . . . . . . . . . . 83--102
              J. Karhumäki   Equations over finite sets of words and
                                  equivalence problems in automata theory  103--118
            Masashi Katsura and   
                 Genjiro Tanaka   Groups of finite elementary codes  . . . 119--149
                  Michael Kunze   Standard automata and semidirect
                                  products of transformation semigroups    151--171
                Liang Zhang and   
                   Weide D. Qiu   Decompositions of recognizable strong
                                  maximal codes  . . . . . . . . . . . . . 173--183

Theoretical Computer Science
Volume 108, Number 2, February 15, 1993

                   Z. Fulop and   
                F. Herrmann and   
               S. Vagvolgyi and   
                      H. Vogler   Tree transducers with external functions 185--236
                Do Long Van and   
                 B. Le Saec and   
                    I. Litovsky   Stability for the zigzag submonoids  . . 237--249
                 M. Madonia and   
                  S. Salemi and   
                   T. Sportelli   A generalization of Sardinas and
                                  Patterson's algorithm to $z$-codes . . . 251--270
          M. Dietzfelbinger and   
                       W. Maass   The complexity of matrix transposition
                                  on one-tape off-line Turing machines
                                  with output tape . . . . . . . . . . . . 271--290
                      U. Schmid   The average CRI-length of a controlled
                                  ALOHA collision resolution algorithm . . 291--310
          Reuven Bar Yehuda and   
                Tuvi Etzion and   
                   Shlomo Moran   Rotating-table games and derivatives of
                                  words  . . . . . . . . . . . . . . . . . 311--329
             Alberto Apostolico   Efficient CRCW-PRAM algorithms for
                                  universal substring searching  . . . . . 331--344
                 Roberto Grossi   On finding common subtrees . . . . . . . 345--356
               Karine Slowinski   Picture words with invisible lines . . . 357--363
                  M. Middendorf   The shortest common nonsubsequence
                                  problem is NP-complete . . . . . . . . . 365--369
           Fabrizio d'Amore and   
Alberto Marchetti-Spaccamela and   
                  Umberto Nanni   The weighted list update problem and the
                                  lazy adversary . . . . . . . . . . . . . 371--384
                        S. Lehr   Sums and rational multiples of
                                  $q$-automatic sequences are
                                  $q$-automatic  . . . . . . . . . . . . . 385--391
          Juraj Hromkovi\vc and   
                 Katsushi Inoue   A note on realtime one-way synchronized
                                  alternating one-counter automata . . . . 393--400


Theoretical Computer Science
Volume 109, Number 1-2, March 01, 1993

                      Anonymous   International Workshop on Computing by
                                  Graph Transformation . . . . . . . . . . ??
               B. Courcelle and   
                   G. Rozenberg   Preface  . . . . . . . . . . . . . . . . 1

Theoretical Computer Science
Volume 109, Number 1--2, March 01, 1993

                   H. Ehrig and   
                   M. Löwe   The ESPRIT Basic Research Working Group
                                  COMPUGRAPH: ``Computing by Graph
                                  Transformation'': a survey . . . . . . . 3--6
           Andrea Corradini and   
                Francesca Rossi   Hyperedge replacement jungle rewriting
                                  for term-rewriting systems and logic
                                  programming  . . . . . . . . . . . . . . 7--48
               B. Courcelle and   
                      M. Mosbah   Monadic second-order evaluations on
                                  tree-decomposable graphs . . . . . . . . 49--82
                   Frank Drewes   Recognising $k$-connected hypergraphs in
                                  cubic time . . . . . . . . . . . . . . . 83--122
                   H. Ehrig and   
                   M. Löwe   Parallel and distributed derivations in
                                  the single-pushout approach  . . . . . . 123--143
                    D. Janssens   Equivalence of computations in actor
                                  grammars . . . . . . . . . . . . . . . . 145--180
              Michael Löwe   Algebraic approach to single-pushout
                                  graph transformation . . . . . . . . . . 181--224
              Ugo Montanari and   
                Francesca Rossi   Graph rewriting for a partial ordering
                                  semantics of concurrent constraint
                                  programming  . . . . . . . . . . . . . . 225--256
                H. J. Schneider   On categorical graph grammars
                                  integrating structural transformations
                                  and operations on labels . . . . . . . . 257--274


Theoretical Computer Science
Volume 110, Number 1, March 15, 1993

           Joost Engelfriet and   
          Hendrik Jan Hoogeboom   $X$-automata on $\omega$-words . . . . . 1--51
                 Eric Goles and   
            Alejandro Maass and   
                Servet Martinez   On the limit set of some universal
                                  cellular automata  . . . . . . . . . . . 53--78
               Wayne D. Blizard   Dedekind multisets and function shells   79--98
           Boaz Patt-Shamir and   
                    David Peleg   Time-space tradeoffs for set operations  99--129
               R. Freivalds and   
               E. B. Kinber and   
                    R. Wiehagen   On the power of inductive inference from
                                  good examples  . . . . . . . . . . . . . 131--144
             Annegret Habel and   
    Hans-Jörg Kreowski and   
              Clemens Lautemann   A comparison of compatible, finite, and
                                  inductive graph properties . . . . . . . 145--168
                  Uri Zwick and   
            Michael S. Paterson   The memory game  . . . . . . . . . . . . 169--196
             A. S. Fraenkel and   
                    S. Simonson   Geography (mathematical games) . . . . . 197--214
             Hans L. Bodlaender   Complexity of path-forming games . . . . 215--245

Theoretical Computer Science
Volume 110, Number 2, March 29, 1993

                       M. Nivat   Editorial introducing the Tutorial
                                  Section  . . . . . . . . . . . . . . . . 247
                   Jean Gallier   Constructive logics. Part I: A tutorial
                                  on proof systems and typed
                                  $\lambda$-calculi  . . . . . . . . . . . 249--339
        Bernadette Charron-Bost   Coupling coefficients of a distributed
                                  execution  . . . . . . . . . . . . . . . 341--376
               Michael J. Maher   A transformation system for deductive
                                  database modules with perfect model
                                  semantics  . . . . . . . . . . . . . . . 377--403
                 Thomas Forster   A semantic characterization of the
                                  well-typed formulae of
                                  $\lambda$-calculus . . . . . . . . . . . 405--418
                M. Sprenger and   
            M. Wymann-Böni   How to decide the lark (combinatorial
                                  logic) . . . . . . . . . . . . . . . . . 419--432


Theoretical Computer Science
Volume 111, Number 1--2, April 12, 1993

                      Anonymous   Sixth Workshop on the Mathematical
                                  Foundations of Programming Semantics . . ??
                 M. Mislove and   
                  R. D. Tennent   Foreword . . . . . . . . . . . . . . . . 1
                Samson Abramsky   Computational interpretations of linear
                                  logic  . . . . . . . . . . . . . . . . . 3--57
              Reinhold Heckmann   Power domains and second-order
                                  predicates . . . . . . . . . . . . . . . 59--88
                 Manfred Droste   On stable domains  . . . . . . . . . . . 89--101
       François Lamarche   Stable domains are generalized
                                  topological spaces . . . . . . . . . . . 103--123
                Michael G. Main   Complete proof rules for strong fairness
                                  and strong extreme fairness  . . . . . . 125--143
         Hans Dybkjær and   
                  Austin Melton   Comparing Hagino's categorical
                                  programming language and typed
                                  lambda-calculi . . . . . . . . . . . . . 145--189
           Lawrence S. Moss and   
               Satish R. Thatte   Modal logic and algebraic specifications 191--210
            Paul C. Gilmore and   
              George K. Tsiknis   A logic for category theory  . . . . . . 211--252
            Paul C. Gilmore and   
              George K. Tsiknis   Logical foundations for programming
                                  semantics  . . . . . . . . . . . . . . . 253--290


Theoretical Computer Science
Volume 112, Number 1, April 26, 1993

                         T. Rus   Editorial  . . . . . . . . . . . . . . . 1
            Ryszard Janicki and   
                  Maciej Koutny   Structure of concurrency . . . . . . . . 5--52
         Yellamraju V. Srinivas   A sheaf-theoretic approach to pattern
                                  matching and related problems  . . . . . 53--97
                Carolyn Talcott   A theory of binding structures and
                                  applications to rewriting  . . . . . . . 99--143
               Muffy Thomas and   
                    Phil Watson   Solving divergence in Knuth--Bendix
                                  completion by enriching signatures . . . 145--185

Theoretical Computer Science
Volume 112, Number 2, May 10, 1993

              Thomas Herbst and   
              Richard M. Thomas   Group presentations, formal languages
                                  and characterizations of one-counter
                                  groups . . . . . . . . . . . . . . . . . 187--214
         Richard D. Bourgin and   
                  Sally E. Howe   Shortest curves in planar regions with
                                  curved boundary  . . . . . . . . . . . . 215--253
          Mitsunori Ogiwara and   
                  Antoni Lozano   On sparse hard sets for counting classes 255--275
Erzsébet Csuhaj-Varjú and   
        Alica Kelemenová   Descriptional complexity of context-free
                                  grammar forms  . . . . . . . . . . . . . 277--289
            Carl Sturtivant and   
     Gudmund Skovbjerg Frandsen   The computational efficacy of
                                  finite-field arithmetic  . . . . . . . . 291--309
             Jean Néraud   Deciding whether a finite set of words
                                  has rank at most two . . . . . . . . . . 311--337
     Jean-Daniel Boissonnat and   
               Monique Teillaud   On the randomized construction of the
                                  Delaunay tree  . . . . . . . . . . . . . 339--354
             Javed A. Aslam and   
                   Aditi Dhagat   On-line algorithms for $2$-coloring
                                  hypergraphs via chip games . . . . . . . 355--369
        Aviezri S. Fraenkel and   
      Edward R. Scheinerman and   
                  Daniel Ullman   Undirected edge geography  . . . . . . . 371--382
            Cristian Calude and   
           Cezar Câmpeanu   Note on the topological structure of
                                  random strings . . . . . . . . . . . . . 383--390
            Oscar H. Ibarra and   
         Nicholas Q. Trân   A note on simple programs with two
                                  variables  . . . . . . . . . . . . . . . 391--397
                     Ivan Korec   Irrational speeds of configurations
                                  growth in generalized Pascal triangles   399--412
            Jerzy Skurczy\'nski   The Borel hierarchy is infinite in the
                                  class of regular sets of trees . . . . . 413--418
       Ondrej Sýkora and   
                  Imrich Vr\vto   Edge separators for graphs of bounded
                                  genus with applications  . . . . . . . . 419--420


Theoretical Computer Science
Volume 113, Number 1, May 24, 1993

                C. Choffrut and   
                     M. Jantzen   Editorial  . . . . . . . . . . . . . . . 1
                 Luc Albert and   
               Rafael Casas and   
          François Fages   Average-case analysis of unification
                                  algorithms . . . . . . . . . . . . . . . 3--34
                 Volker Diekert   On the concatenation of infinite traces  35--54
              Lance Fortnow and   
                   Carsten Lund   Interactive proof systems and
                                  alternating time-space complexity  . . . 55--73
              Martin Hühne   On the power of several queues (Turing
                                  machines)  . . . . . . . . . . . . . . . 75--91
       Thierry Jéron and   
                    Claude Jard   Testing for unboundedness of fifo
                                  channels . . . . . . . . . . . . . . . . 93--117
                K. Madlener and   
               P. Narendran and   
                    F. Otto and   
                       L. Zhang   On weakly confluent monadic
                                  string-rewriting systems . . . . . . . . 119--165
                      Jun Tarui   Probabilistic polynomials, $AC^{0}$
                                  functions, and the polynomial-time
                                  hierarchly . . . . . . . . . . . . . . . 167--183

Theoretical Computer Science
Volume 113, Number 2, June 07, 1993

                Klaus Weihrauch   Computability on computable metric
                                  spaces . . . . . . . . . . . . . . . . . 191--210
                      Bo Yi and   
                       Jiafu Xu   Analogy calculus . . . . . . . . . . . . 211--230
                      Lu Ruqian   A true concurrency model of CCS
                                  semantics  . . . . . . . . . . . . . . . 231--258
                 Jianguo Lu and   
                       Jiafu Xu   Analogical program derivation based on
                                  type theory  . . . . . . . . . . . . . . 259--272
        Antonio Bucciarelli and   
                 Thomas Ehrhard   A theory of sequentiality  . . . . . . . 273--291
        Rob J. van Glabbeek and   
            Frits W. Vaandrager   Modular specification of process
                                  algebras . . . . . . . . . . . . . . . . 293--348
                M. Masseron and   
                   C. Tollu and   
                  J. Vauzeilles   Generating plans in linear logic I.
                                  Actions as proofs  . . . . . . . . . . . 349--370
                    M. Masseron   Generating plans in linear logic. II. A
                                  geometry of conjunctive actions  . . . . 371--375


Theoretical Computer Science
Volume 114, Number 1, June 14, 1993

                      Anonymous   3rd Workshop on Concurrency and
                                  Compositionality . . . . . . . . . . . . ??
                    E. Best and   
                   G. Rozenberg   Preface  . . . . . . . . . . . . . . . . 1
        Martín Abadi and   
              Gordon D. Plotkin   A logical view of composition  . . . . . 3--30
                  G. Boudol and   
              I. Castellani and   
                M. Hennessy and   
                       A. Kiehn   Observing localities . . . . . . . . . . 31--61
           Pierpaolo Degano and   
            Rocco De Nicola and   
                  Ugo Montanari   Universal axioms for bisimulations . . . 63--91
            Jörg Desel and   
                 Javier Esparza   Reachability in cyclic extended
                                  free-choice systems  . . . . . . . . . . 93--118
          Kim Guldstrand Larsen   The expressive power of implicit
                                  specifications . . . . . . . . . . . . . 119--147
               Robin Milner and   
             Joachim Parrow and   
                   David Walker   Modal logics for mobile processes  . . . 149--171
                  Walter Vogler   Bisimulation and action refinement . . . 173--200

Theoretical Computer Science
Volume 114, Number 2, June 21, 1993

                 Steven Vickers   Information systems for continuous
                                  posets . . . . . . . . . . . . . . . . . 201--229
               Thomas Eiter and   
                  Georg Gottlob   Propositional circumscription and
                                  extended closed-world reasoning are
                                  $\Pi^P_2$-complete . . . . . . . . . . . 231--245
           Jules Desharnais and   
                  Ali Jaoua and   
                 Fatma Mili and   
        Noureddine Boudriga and   
                       Ali Mili   A relational division operator: the
                                  conjugate kernel . . . . . . . . . . . . 247--272
            Daniel J. Dougherty   Higher-order unification via combinators 273--298
                   Michael Barr   Terminal coalgebras in well-founded set
                                  theory . . . . . . . . . . . . . . . . . 299--315
Morten Elvang-Gòransson and   
                       Olaf Owe   A simple sequent calculus for partial
                                  functions  . . . . . . . . . . . . . . . 317--330


Theoretical Computer Science
Volume 115, Number 1, July 05, 1993

                S. Abramsky and   
                    P.-L Curien   Preface  . . . . . . . . . . . . . . . . 1
                  Richard Blute   Linear logic, coherence and dinaturality 3--41
                 Albert Burroni   Higher-dimensional word problems with
                                  applications to equational logic . . . . 43--62
                Thierry Coquand   Another proof of the intuitionistic
                                  Ramsey theorem . . . . . . . . . . . . . 63--75
               Abbas Edalat and   
               Michael B. Smyth   I-categories as a framework for solving
                                  domain equations . . . . . . . . . . . . 77--106
                       P. Freyd   Structural polymorphism  . . . . . . . . 107--129
            Grzegorz Jarzembski   Programs in partial algebras . . . . . . 131--149
                   C. Barry Jay   Tail recursion through universal
                                  invariants . . . . . . . . . . . . . . . 151--189

Theoretical Computer Science
Volume 115, Number 2, July 19, 1993

              Igor Litovsky and   
           Yves Métivier   Computing with graph rewriting systems
                                  with priorities  . . . . . . . . . . . . 191--224
              Eric Allender and   
             Richard Beigel and   
           Ulrich Hertrampf and   
                   Steven Homer   Almost-everywhere complexity hierarchies
                                  for nondeterministic time  . . . . . . . 225--241
                   Arturo Carpi   Overlap-free words and finite automata   243--260
            Oscar H. Ibarra and   
         Nicholas Q. Trân   Synchronized finite automata and $2$DFA
                                  reductions . . . . . . . . . . . . . . . 261--275
         Luc Longpré and   
                 Alan L. Selman   Hard promise problems and nonuniform
                                  complexity . . . . . . . . . . . . . . . 277--290
                     A. Troesch   Interpretation geométrique de
                                  l'algorithme d'Euclide et reconnaissance
                                  de segments. (French) [Geometric
                                  interpretation of Euclid's algorithm
                                  with recognition segments] . . . . . . . 291--319
                 Eric Goles and   
                 Marcos A. Kiwi   Games on line graphs and sand piles  . . 321--349
                 R. Srikant and   
              Ravi Sundaram and   
           Karan Sher Singh and   
                C. Pandu Rangan   Optimal path cover problem on block
                                  graphs and bipartite permutation graphs  351--357
            Masashi Katsura and   
                 Yuji Kobayashi   The shuffle algebra and its derivations  359--369
               Shouwen Tang and   
                     Bin Fu and   
                       Tian Liu   Exponential-time and subexponential-time
                                  sets . . . . . . . . . . . . . . . . . . 371--381
               Steven Homer and   
               Stuart Kurtz and   
                    James Royer   On $1$-truth-table-hard languages  . . . 383--389
Sándor Vágvölgyi   A fast algorithm for constructing a tree
                                  automaton recognizing a congruential
                                  tree language  . . . . . . . . . . . . . 391--399


Theoretical Computer Science
Volume 116, Number 1, August 02, 1993

               S. Abiteboul and   
                  P. Kanellakis   Foreword . . . . . . . . . . . . . . . . 1
                   Ronald Fagin   Finite-model theory --- a personal
                                  perspective  . . . . . . . . . . . . . . 3--31
           Gabriel M. Kuper and   
                 Moshe Y. Vardi   On the complexity of queries in the
                                  logical data model . . . . . . . . . . . 33--57
              Catriel Beeri and   
                Yoram Kornatzky   Algebraic optimization of
                                  object-oriented query languages  . . . . 59--94
         Mariano P. Consens and   
           Alberto O. Mendelzon   Low-complexity aggregation in GraphLog
                                  and Datalog  . . . . . . . . . . . . . . 95--116
                Peter Z. Revesz   A closed-form evaluation for Datalog
                                  queries with integer (gap)-order
                                  constraints  . . . . . . . . . . . . . . 117--149
             Ron van der Meyden   Recursively indefinite databases . . . . 151--194
          Richard J. Lipton and   
        Jeffrey F. Naughton and   
       Donovan A. Schneider and   
                    S. Seshadri   Efficient sampling strategies for
                                  relational database operations . . . . . 195--226

Theoretical Computer Science
Volume 116, Number 2, August 16, 1993

             A. Ehrenfeucht and   
                   G. Rozenberg   $T$-Structures, $T$-functions and texts  227--290
            Beat Brüderlin   Using geometric rewrite rules for
                                  solving geometric problems symbolically  291--303
      Juhani Karhumäki and   
            Wojciech Rytter and   
               Stefan Jarominek   Efficient constructions of test sets for
                                  regular and context-free languages . . . 305--316
            Yannick Saouter and   
                Patrice Quinton   Computability of recurrence equations    317--337
          Mircea Andra\csiu and   
            Gheorghe P\uaun and   
         Jürgen Dassow and   
                   Arto Salomaa   Language-theoretic problems arising from
                                  Richelieu cryptosystems  . . . . . . . . 339--357
         Esteban Feuerstein and   
   Alberto Marchetti-Spaccamela   Dynamic algorithms for shortest paths in
                                  planar graphs  . . . . . . . . . . . . . 359--371
             Karel Culik II and   
                    Simant Dube   Affine automata and related techniques
                                  for generation of complex images . . . . 373--398
              Elias Koutsoupias   Improvements on Khrapchenko's theorem    399--403
        Hans Kleine Büning   On generalized Horn formulas and
                                  $k$-resolution . . . . . . . . . . . . . 405--413
        Pavel Pudlák and   
            Petr Savický   On shifting networks (Boolean circuit)   415--419
            Burkhard Monien and   
            Wojciech Rytter and   
          Leopold Schäpers   Fast recognition of deterministic CFL's
                                  with a smaller number of processors  . . 421--429


Theoretical Computer Science
Volume 117, Number 1--2, August 30, 1993

                      Anonymous   Conference on Formal Power Series and
                                  Algebraic Combinatorics  . . . . . . . . ??
                  M. Delest and   
                   G. Jacob and   
                      P. Leroux   Forward  . . . . . . . . . . . . . . . . 1
                Gilbert Labelle   Sur la symétrie et l'asymétrie des
                                  structures combinatoires. (French) [On
                                  the symmetry and asymmetry of
                                  combinatorial structures]  . . . . . . . 3--22
               Doron Zeilberger   Identities in search of identity . . . . 23--38
               Marcella Anselmo   The operation $\uparrow$ on formal power
                                  series . . . . . . . . . . . . . . . . . 39--43
              Didier Arques and   
               Isabelle Jacques   Classification des cartes pointées de
                                  genre $1$ et relation fonctionnelle
                                  associée. (French) [Classification of
                                  genus-$1$ pointed maps and associated
                                  functional relation] . . . . . . . . . . 45--65
   J. Bétréma and   
                   J. G. Penaud   Animaux et arbres guingois. (French)
                                  [Animals and lop-sided trees]  . . . . . 67--89
            Anders Björner   The Möbius function of factor order . . . 91--98
                   R. Casas and   
             J. Díaz and   
             C. Martínez   Average-case analysis on simple families
                                  of trees using a balanced probability
                                  model  . . . . . . . . . . . . . . . . . 99--112
             William Y. C. Chen   Context-free grammars, differential
                                  operators and formal power series  . . . 113--130
                 Yves Chiricota   Représentation symbolique d'esp\`eces
                                  moléculaires. (French) [Symbolic
                                  representation of molecular species] . . 131--136
              Seul Hee Choi and   
    Dominique Gouyou-Beauchamps   Enumeration of generalized Young
                                  tableaux with bounded height . . . . . . 137--151
               I. Constantineau   Auto-similarité dans la combinatoire des
                                  polynômes orthogonaux. (French)
                                  [Auto-similarity in the combination of
                                  orthogonal polynomials]  . . . . . . . . 153--167
 Hél\`ene Décoste   Séries indicatrices et $q$-séries.
                                  (French) [Indicator series and
                                  $q$-series]  . . . . . . . . . . . . . . 169--186
                  S. Dulucq and   
                        S. Gire   Complexité d'algorithmes et opérations sur
                                  les arbres. (French) [Algorithmic
                                  complexity and operations on trees]  . . 187--198
               Shalosh B. Ekhad   A short, elementary, and easy, WZ proof
                                  of the Askey-Gasper inequality that was
                                  used by de Branges in his proof of the
                                  Bieberbach conjecture  . . . . . . . . . 199--202
                  J. C. Lalanne   Sur une involution sur les chemins de
                                  Dyck. (French) [On an involution on Dyck
                                  paths] . . . . . . . . . . . . . . . . . 203--215
                 Pierre Lalonde   Bases de Lyndon des alg\`ebres de Lie
                                  libres partiellement commutatives.
                                  (French) [Lyndon bases for partially
                                  commutative free Lie algebras] . . . . . 217--226
                S. K. Lando and   
                  A. K. Zvonkin   Plane and projective meanders  . . . . . 227--241
                Roberto Mantaci   Sur la distribution des anti-excédances
                                  dans le groupe symétrique et dans ses
                                  sousgroupes. (French) [On the
                                  anti-exceedance distribution in a
                                  symmetrical group in its sub-groups] . . 243--253
            Guy Melançon   Constructions des bases standard des
                                  $K<A>$-modules \`a droite. (French)
                                  [Construction of standard bases for
                                  right $K<A>$-modules]  . . . . . . . . . . 255--272
                 Bruce E. Sagan   Combinatorial proofs of hook generating
                                  functions for skew plane partitions  . . 273--287
                Dragutin Svrtan   New plethysm operation, Chern characters
                                  of exterior and symmetric powers with
                                  applications to Stiefel-Whitney classes
                                  of Grassmannians . . . . . . . . . . . . 289--301
                    Julian West   Sorting twice through a stack  . . . . . 303--313


Theoretical Computer Science
Volume 118, Number 1, September 13, 1993

                       B. Rovan   Introduction . . . . . . . . . . . . . . 1
           Sanjoy K. Baruah and   
           Rodney R. Howell and   
                Louis E. Rosier   Feasibility problems for recurring tasks
                                  on one processor . . . . . . . . . . . . 3--20
         Philippe Darondeau and   
               Pierpaolo Degano   Refinement of actions in event
                                  structures and causal trees  . . . . . . 21--48
                 Viliam Geffert   A speed-up theorem without tape
                                  compression  . . . . . . . . . . . . . . 49--65
               Igor Walukiewicz   Gentzen-type axiomatization for PAL  . . 67--79
                   Ingo Wegener   BOTTOM-UP-HEAP\-SORT, a new variant of
                                  HEAP\-SORT, beating, on an average,
                                  QUICK\-SORT (if $n$ is not very small)   81--98

Theoretical Computer Science
Volume 118, Number 2, September 27, 1993

               Pierre Deransart   Proof methods of declarative properties
                                  of definite programs . . . . . . . . . . 99--166
                   Hubert Comon   Complete axiomatizations of some
                                  quotient term algebras . . . . . . . . . 167--191
                Iain A. Stewart   Methods for proving completeness via
                                  logical reductions . . . . . . . . . . . 193--229
             M. Draghicescu and   
               S. Purushothaman   A uniform treatment of order of
                                  evaluation and aggregate update  . . . . 231--262
               Jan Friso Groote   Transition system specifications with
                                  negative premises  . . . . . . . . . . . 263--299
                Alex K. Simpson   A characterisation of the
                                  least-fixed-point operator by
                                  dinaturality . . . . . . . . . . . . . . 301--314
               Thomas Eiter and   
                  Georg Gottlob   Erratum: Propositional circumscription
                                  and extended closed-world reasoning are
                                  $\Pi^P_2$-complete . . . . . . . . . . . 315--315


Theoretical Computer Science
Volume 119, Number 1, October 11, 1993

                      Anonymous   5th Soviet --- French Symposium on
                                  Theoretical Computer Science, Methods
                                  and Tools for Compilation, and Program
                                  Development (Informatika '91)  . . . . . ??
                  Kablan Barbar   Attributed tree grammars . . . . . . . . 3--22
              M.-M. Corsini and   
                     K. Musumbu   Type inference in Prolog: a new approach 23--38
          Philippe Devienne and   
          Patrick Leb\`egue and   
                    Max Dauchet   Weighted systems of equations  . . . . . 39--62
                A. Ja. Dikovsky   On computational complexity of Prolog
                                  programs . . . . . . . . . . . . . . . . 63--102
                   Walter Dosch   On a generalized product for domains . . 103--125
                   Zineb Habbas   A complete modal proof system for HAL:
                                  the Herbrand agent language  . . . . . . 127--143
          A. A. Letichevsky and   
           J. V. Kapitonova and   
                S. V. Konozenko   Computations in APS (algebraic
                                  programming system)  . . . . . . . . . . 145--171
         V. A. Nepomniaschy and   
                  A. A. Sulimov   Problem-oriented verification system and
                                  its application to linear algebra
                                  programs . . . . . . . . . . . . . . . . 173--185
            Vladimir Yu Sazonov   Hereditarily-finite sets, data bases and
                                  polynomial-time computability  . . . . . 187--214
                A. O. Slissenko   On fault tolerance of syntax . . . . . . 215--222
                   M. K. Valiev   $P^1_1$-universality of some
                                  propositional logics of concurrent
                                  programs . . . . . . . . . . . . . . . . 223--232

Theoretical Computer Science
Volume 119, Number 2, October 25, 1993

            Miroslaw Kutylowski   Stack versus sensitivity for one-way
                                  automata . . . . . . . . . . . . . . . . 233--245
         Alberto Apostolico and   
            Andrzej Ehrenfeucht   Efficient detection of
                                  quasiperiodicities in strings  . . . . . 247--265
            Jean-Camille Birget   Partial orders on words, minimal
                                  elements of regular languages, and state
                                  complexity . . . . . . . . . . . . . . . 267--291
                  Marius Zimand   If not empty, NP-P is topologically
                                  large  . . . . . . . . . . . . . . . . . 293--310
          Walter Stromquist and   
                  Daniel Ullman   Sequential compounds of combinatorial
                                  games  . . . . . . . . . . . . . . . . . 311--321
                    David Wolfe   Snakes in Domineering games  . . . . . . 323--329
           Roberto Tamassia and   
              Ioannis G. Tollis   Dynamic reachability in planar digraphs
                                  with one source and one sink . . . . . . 331--343
                   B. Litow and   
                      Ph. Dumas   Additive cellular automata and algebraic
                                  series . . . . . . . . . . . . . . . . . 345--354
             B. John Oommen and   
                 David T. H. Ng   An optimal absorbing list organization
                                  strategy with constant memory
                                  requirements . . . . . . . . . . . . . . 355--361
                  Tao Jiang and   
                        Ming Li   On the complexity of learning strings
                                  and sequences  . . . . . . . . . . . . . 363--371


Theoretical Computer Science
Volume 120, Number 1, November 08, 1993

                   E. Knill and   
                  P. T. Cox and   
               T. Pietrzykowski   Equality and abductive residua for Horn
                                  clauses  . . . . . . . . . . . . . . . . 1--44
                    G. Nota and   
                 S. Orefice and   
                  G. Pacini and   
                F. Ruggiero and   
                     G. Tortora   Legality concepts for three-valued logic
                                  programs . . . . . . . . . . . . . . . . 45--68
               Michal Grabowski   On the status of proving program
                                  properties in effective interpretations  69--81
              Stefano Baratella   A class of programs for which SLDNF
                                  resolution and NAF rule are complete . . 83--99
                Paul Gastin and   
                 Brigitte Rozoy   The poset of infinitary traces . . . . . 101--121
                  P. Cousot and   
                      R. Cousot   ``A la Burstall'' intermittent
                                  assertions induction principles for
                                  proving inevitability properties of
                                  programs . . . . . . . . . . . . . . . . 123--155
                   Wenhui Zhang   Cut formulas in propositional logic  . . 157--168

Theoretical Computer Science
Volume 120, Number 2, November 22, 1993

                   Yves Marcoux   Composition is almost (but not quite) as
                                  good as $s-1-1$  . . . . . . . . . . . . 169--195
     Anne Brüggemann-Klein   Regular expressions into finite automata 197--213
           Gen-Huey H. Chen and   
         Biing-Feng F. Wang and   
                     Hungwen Li   Deriving algorithms on reconfigurable
                                  networks based on function decomposition 215--227
                   Juha Honkala   On D$0$L systems with immigration  . . . 229--245
              Changwook Kim and   
                  Dong Hoon Lee   Separating $k$-separated eNCE graph
                                  languages  . . . . . . . . . . . . . . . 247--259
      Rajanarayanan Subbiah and   
       Sitharama S. Iyengar and   
      Sridhar Radhakrishnan and   
                  R. L. Kashyap   An optimal distributed algorithm for
                                  recognizing mesh-connected networks  . . 261--278
                     Bin Fu and   
                   Hong-zhou Li   On symmetric differences of NP-hard sets
                                  with weakly P-selective sets . . . . . . 279--291
            Gheorghe P\uaun and   
                   Arto Salomaa   Closure properties of slender languages  293--301
                   Klaas Sikkel   Parallel on-line parsing in constant
                                  time per word  . . . . . . . . . . . . . 303--310
                    A. Ferreira   On space-efficient algorithms for
                                  certain NP-complete problems . . . . . . 311--315


Theoretical Computer Science
Volume 121, Number 1--2, December 06, 1993

                   M. Abadi and   
                L. Cardelli and   
                    P.-L Curien   A short scientific biography of Corrado
                                  Bohm . . . . . . . . . . . . . . . . . . 1
                   M. Abadi and   
                L. Cardelli and   
                   P.-L. Curien   Formal parametric polymorphism . . . . . 9--58
                Henk Barendregt   Constructive proofs of the range
                                  property in lambda calculus  . . . . . . 59--69
      Alessandro Berarducci and   
            Benedetto Intrigila   Some new results on easy lambda-terms    71--88
        Robert L. Constable and   
                 Scott F. Smith   Computational foundations of basic
                                  recursive function theory  . . . . . . . 89--112
                Mario Coppo and   
                Alberto Ferrari   Type inference, abstract interpretation
                                  and strictness analysis  . . . . . . . . 113--143
             Gérard Huet   An analysis of Böhm's theorem . . . . . . 145--167
                G. Jacopini and   
                   G. Sontacchi   General recursive functions in a very
                                  simply interpretable typed
                                  $\lambda$-calculus . . . . . . . . . . . 169--178
                Stephen Brookes   Historical introduction to ``Concrete
                                  domains'' by G. Kahn and G. D. Plotkin   179--186
                    G. Kahn and   
                  G. D. Plotkin   Concrete domains (programming languages
                                  semantics) . . . . . . . . . . . . . . . 187--277
            Jan Willem Klop and   
        Vincent van Oostrom and   
            Femke van Raamsdonk   Combinatory reduction systems:
                                  introduction and survey  . . . . . . . . 279--308
                 Daniel Leivant   Functions over free algebras definable
                                  in the simply typed lambda calculus  . . 309--321
             Giuseppe Longo and   
           Kathleen Milsted and   
                Sergei Soloviev   The genericity theorem and parametricity
                                  in the polymorphic $\lambda$-calculus    323--349
              Gordon D. Plotkin   Set-theoretical and other elementary
                                  models of the $\lambda$-calculus . . . . 351--409
                  Dana S. Scott   A type-theoretical alternative to ISWIM,
                                  CUCH, OWHY . . . . . . . . . . . . . . . 411--440
                   Rick Statman   Some examples of non-existent
                                  combinators  . . . . . . . . . . . . . . 441--448


Theoretical Computer Science
Volume 122, Number 1--2, January 03, 1994

                    S. Goto and   
                       K. Satoh   Preface to the Special Issue of Selected
                                  Papers of the Fifth Generation Computer
                                  Systems Conference, Tokyo, June 1--5,
                                  1992 . . . . . . . . . . . . . . . . . . 1
                   A. Bossi and   
              M. Gabbrielli and   
                    G. Levi and   
                      M. C. Meo   A compositional semantics for logic
                                  programs . . . . . . . . . . . . . . . . 3--47
  Luís Moniz Pereira and   
     José J. Alferes and   
     Joaquim N. Aparício   Adding closed world assumptions to
                                  well-founded semantics . . . . . . . . . 49--68
               Tadashi Kawamura   Logic program synthesis from first-order
                                  logic specifications . . . . . . . . . . 69--96
               Bern Martens and   
           Danny De Schreye and   
    Tamás Horváth   Sound and complete partial deduction
                                  with unfolding based on well-founded
                                  measures . . . . . . . . . . . . . . . . 97--117
                 Makoto Tatsuta   Realizability interpretation of
                                  coinductive definitions and program
                                  synthesis with streams . . . . . . . . . 119--136
              Yukihide Takayama   Defining concurrent processes
                                  constructively . . . . . . . . . . . . . 137--164
           Andrea Corradini and   
              Ugo Montanari and   
                Francesca Rossi   An abstract machine for concurrent
                                  modular systems: CHARM . . . . . . . . . 165--200
                    V. Poirriez   MLOG: a strongly typed confluent
                                  functional language with logical
                                  variables  . . . . . . . . . . . . . . . 201--223
              Marc Denecker and   
               Danny De Schreye   On the duality of abduction and model
                                  generation in a framework for model
                                  generation with equality . . . . . . . . 225--262
         Hassan A\"\it-Kaci and   
           Andreas Podelski and   
                    Gert Smolka   A feature constraint system for logic
                                  programming with entailment  . . . . . . 263--283


Theoretical Computer Science
Volume 123, Number 1, January 17, 1994

                      Anonymous   10th `Journées Mathématiques-Informatique'
                                  (Mathematics --- Computer Science) . . . ??
             Jean-Paul Allouche   Note on the cyclic Towers of Hanoi . . . 3--7
         Marc Roland Assous and   
   Vincent Bouchitté and   
       Christine Charretton and   
                 Brigitte Rozoy   Finite labelling problem in event
                                  structures . . . . . . . . . . . . . . . 9--19
                    A. Bertrand   Sur une conjecture d'Yves Métivier.
                                  (French) [On a conjecture of Yves
                                  Métivier (rewriting system)]  . . . . . . 21--30
                Claude Bertrand   A natural semantics of first-order type
                                  dependency . . . . . . . . . . . . . . . 31--53
               F. Blanchard and   
                       S. Fabre   Quelques procédés engendrant des suites
                                  infinies. (French) [Some production
                                  procedures of infinite sequences]  . . . 55--60
              Jean-Pierre Borel   Symbolic representation of piecewise
                                  linear functions on the unit interval
                                  and application to discrepancy . . . . . 61--87
            Claude Chaunier and   
                  Nik Lygero\=s   Le nombre de posets \`a isomorphie
                                  pr\`es ayant $12$ éléments. (French) [The
                                  number of nearly isomorphic posets
                                  having $12$ elements]  . . . . . . . . . 89--94
  Hervé Daudé and   
         Brigitte Vallée   An upper bound on the average number of
                                  iterations of the LLL algorithm  . . . . 95--115
            Dominique Duval and   
Pascale Sénéchaud   Sketches and parametrization . . . . . . 117--130
                    Henri Faure   Multidimensional quasi Monte-Carlo
                                  methods  . . . . . . . . . . . . . . . . 131--137
           Zbigniew S. Kowalski   Multiple returns under a bounded number
                                  of iterations  . . . . . . . . . . . . . 139--144
                    M. Mignotte   Sur l'équation de Catalan. II. (French)
                                  [On Catalan's equation. II (number
                                  theory)] . . . . . . . . . . . . . . . . 145--149
             Eric Rémila   A linear algorithm to tile the trapezes
                                  with $h_m$ and $v_n$ . . . . . . . . . . 151--165
                   Xiangdong Ye   Coexistence of uniquely ergodic
                                  subsystems of interval mapping . . . . . 167--181

Theoretical Computer Science
Volume 123, Number 2, January 31, 1994

              Dung T. Huynh and   
                        Lu Tian   Deciding bisimilarity of normed
                                  context-free processes is in
                                  $\Sigma^p_2$ . . . . . . . . . . . . . . 183--197
                   Bruno Martin   A universal cellular automaton in
                                  quasi-linear time and its S--m--n form   199--237
              F. Blanchet-Sadri   Equations and monoid varieties of
                                  dot-depth one and two  . . . . . . . . . 239--258
                M. Clerbout and   
                    D. Gonzalez   Atomic semicommutations  . . . . . . . . 259--272
        Jean-Camille Birget and   
         Stuart W. Margolis and   
                 John C. Meakin   The word problem for inverse monoids
                                  presented by one idempotent relator  . . 273--289
          Philippe Flajolet and   
              Peter Grabner and   
        Peter Kirschenhofer and   
           Helmut Prodinger and   
                Robert F. Tichy   Mellin transforms and asymptotics:
                                  digital sums . . . . . . . . . . . . . . 291--314
              Kunimasa Aoki and   
             Juichi Shinoda and   
                   Teruko Tsuda   On $\Pi_2$ theories of hp-$T$ degrees of
                                  low sets . . . . . . . . . . . . . . . . 315--327
              Shigeki Iwata and   
                   Takumi Kasai   The Othello game on an $n \times n$
                                  board is PSPACE-complete . . . . . . . . 329--340
                     Daniel Mey   Finite games for a predicate logic
                                  without contractions . . . . . . . . . . 341--349
                Grahame Bennett   Double dipping: the case of the missing
                                  binomial coefficient identities  . . . . 351--375
               Dexter Kozen and   
                    Shmuel Zaks   Optimal bounds for the change-making
                                  problem  . . . . . . . . . . . . . . . . 377--388
                 Maria M. Klawe   Shallow grates . . . . . . . . . . . . . 389--395
                     S. Burckel   Functional equations associated with
                                  congruential functions . . . . . . . . . 397--406
         Edith Hemaspaandra and   
           Lane A. Hemaspaandra   Quasi-injective reductions . . . . . . . 407--413
                Naomi Nishimura   Restricted CRCW PRAMs  . . . . . . . . . 415--426
            Burkhard Monien and   
            Wojciech Rytter and   
           Helmut Schäpers   Fast recognition of deterministic CFL's
                                  with a smaller number of processors
                                  (corrigendum)  . . . . . . . . . . . . . 427--428


Theoretical Computer Science
Volume 124, Number 1, February 14, 1994

    M. E. Majster-Cederbaum and   
                    F. Zetzsche   The comparison of a cpo-based semantics
                                  with a cms-based semantics for CSP . . . 1--40
  Béatrice Bérard   Global serializability of concurrent
                                  programs . . . . . . . . . . . . . . . . 41--70
                Susumu Yamasaki   A denotational semantics and dataflow
                                  construction for logic programs  . . . . 71--91
             Michael Codish and   
                Dennis Dams and   
                   Eyal Yardeni   Bottom-up abstract interpretation of
                                  logic programs . . . . . . . . . . . . . 93--125
               Satish R. Thatte   Type inference with partial types  . . . 127--148
             J. A. Bergstra and   
                     J. Heering   Which data types have omega-complete
                                  initial algebra specifications?  . . . . 149--168
               Ursula Goltz and   
                  Arend Rensink   Finite Petri nets as models for
                                  recursive causal behaviour . . . . . . . 169--179
                     Kees Doets   Left termination turned into termination 180--187
                   Michael Barr   Additions and corrections to ``Terminal
                                  coalgebras in well-founded set theory''  189--192

Theoretical Computer Science
Volume 124, Number 2, February 28, 1994

                Andrew M. Pitts   A co-induction principle for recursively
                                  defined domains  . . . . . . . . . . . . 195--219
                    Malika More   Investigation of binary spectra by
                                  explicit polynomial transformations of
                                  graphs . . . . . . . . . . . . . . . . . 221--272
               Wim H. Hesselink   Nondeterminacy and recursion via stacks
                                  and games  . . . . . . . . . . . . . . . 273--295
                   A. Bossi and   
                   N. Cocco and   
                      M. Fabris   Norms on terms and their use in proving
                                  universal termination of a logic program 297--328
             Jung-Heum Park and   
                Kyung-Yong Chwa   On the construction of regular minimal
                                  broadcast digraphs . . . . . . . . . . . 329--342
    Jean-Jacques Hébrard   A linear algorithm for renaming a set of
                                  clauses as a Horn set  . . . . . . . . . 343--350


Theoretical Computer Science
Volume 125, Number 1, March 14, 1994

                 I. Mitrani and   
                     E. Gelenbe   Preface  . . . . . . . . . . . . . . . . 1
         E. G. Coffman, Jr. and   
             Leopold Flatto and   
               Bjorn Poonen and   
                 Paul E. Wright   The processor minimization problem with
                                  independent waiting-time constraints . . 3--16
         M. B. Combé and   
                    O. J. Boxma   Optimization of static traffic
                                  allocation policies  . . . . . . . . . . 17--43
               Graham Louth and   
       Michael Mitzenmacher and   
                    Frank Kelly   Computational complexity of loss
                                  networks . . . . . . . . . . . . . . . . 45--59
                Micha Hofri and   
                   Yaakov Kogan   Asymptotic analysis of product-form
                                  distributions related to large
                                  interconnection networks . . . . . . . . 61--90
                 Ram Chakka and   
                    Isi Mitrani   Heterogeneous multiprocessor systems
                                  with breakdowns: Performance and optimal
                                  repair strategies  . . . . . . . . . . . 91--109
            Ian F. Akyildiz and   
                Horst von Brand   Exact solutions for networks of queues
                                  with blocking-after-service  . . . . . . 111--130
               Erol Gelenbe and   
      Marisela Hernández   Virus tests to maximize availability of
                                  software systems . . . . . . . . . . . . 131--147
   François Baccelli and   
          William A. Massey and   
                 Paul E. Wright   Determining the exit time distribution
                                  for a closed cyclic network  . . . . . . 149--165

Theoretical Computer Science
Volume 125, Number 2, March 28, 1994

                Paul Gastin and   
              Antoine Petit and   
               Wieslaw Zielonka   An extension of Kleene's and Ochmanski's
                                  theorems to infinite traces  . . . . . . 167--204
              Martin Middendorf   More on the complexity of common
                                  superstring and supersequence problems   205--228
                Mody Lempel and   
                     Azaria Paz   An algorithm for finding a shortest
                                  vector in a two-dimensional modular
                                  lattice  . . . . . . . . . . . . . . . . 229--241
                  Tao Jiang and   
            Oscar H. Ibarra and   
                       Hui Wang   Some results concerning 2-D on-line
                                  tessellation acceptors and 2-D
                                  alternating finite automata  . . . . . . 243--257
             A. Ehrenfeucht and   
                 P. Ten Pas and   
                   G. Rozenberg   Properties of grammatical codes of trees 259--293
                  Marty J. Wolf   Nondeterministic circuits, space
                                  complexity and quasigroups . . . . . . . 295--313
                   Sheng Yu and   
              Qingyu Zhuang and   
                    Kai Salomaa   The state complexities of some basic
                                  operations on regular languages  . . . . 315--328
                     Eric Goles   Lyapunov operators to study the
                                  convergence of extremal automata . . . . 329--337
                       B. Litow   A context-free language decision problem 339--343
               Vineet Bafna and   
       Bala Kalyanasundaram and   
                     Kirk Pruhs   Not all insertion methods yield constant
                                  approximate tours in the Euclidean plane 345--353
             Robert E. Matthews   An inherently iterative algorithm for
                                  the Grzegorczyk hierarchy  . . . . . . . 355--360
             Alexandru Mateescu   Scattered deletion and commutativity . . 361--371
                  Pengyuan Chen   The communication complexity of
                                  computing differentiable functions in a
                                  multicomputer network  . . . . . . . . . 373--383


Theoretical Computer Science
Volume 126, Number 1, April 11, 1994

                    J.-C Raoult   Preface  . . . . . . . . . . . . . . . . 1
           Henrik Reif Andersen   Model checking and Boolean graphs  . . . 3--30
   Anne-Cécile Caron and   
               Jean-Luc Coquide   Decidability of reachability for
                                  disjoint union of term rewriting systems 31--52
                Bruno Courcelle   Monadic second-order definable graph
                                  transductions: a survey  . . . . . . . . 53--75
                       Mads Dam   CTL$*$ and ECTL$*$ as fragments of the
                                  modal $\mu$-calculus . . . . . . . . . . 77--96
               Andreas Potthoff   Modulo-counting quantifiers over finite
                                  trees  . . . . . . . . . . . . . . . . . 97--112
                   Helmut Seidl   Finite tree automata with cost functions 113--142

Theoretical Computer Science
Volume 126, Number 2, April 25, 1994

                Doron Peled and   
                    Amir Pnueli   Proving partial order properties . . . . 143--182
                Rajeev Alur and   
                  David L. Dill   A theory of timed automata . . . . . . . 183--235
              J. A. Gerhard and   
                  Mario Petrich   Unification in free distributive
                                  lattices . . . . . . . . . . . . . . . . 237--257
            Vincent van Oostrom   Confluence by decreasing diagrams  . . . 259--280
                Laurent Regnier   Une equivalence sur les lambda-termes.
                                  (French) [Equivalence between
                                  lambda-terms]  . . . . . . . . . . . . . 281--292


Theoretical Computer Science
Volume 127, Number 1, May 09, 1994

                  C. Hosono and   
                       Y. Ikeda   A formal derivation of the decidability
                                  of the theory SA . . . . . . . . . . . . 1--23
                    Kai Salomaa   Synchronized tree automata . . . . . . . 25--51
               J. W. Daykin and   
           C. S. Iliopoulos and   
                    W. F. Smyth   Parallel RAM algorithms for factorizing
                                  words  . . . . . . . . . . . . . . . . . 53--67
    Jean-Luc Coquidé and   
                Max Dauchet and   
       Rémi Gilleron and   
Sándor Vágvölgyi   Bottom-up tree pushdown automata:
                                  classification and connection with
                                  rewrite systems  . . . . . . . . . . . . 69--98
               B. Codenotti and   
                M. Leoncini and   
                       G. Resta   Oracle computations in parallel
                                  numerical linear algebra . . . . . . . . 99--121
          Juraj Hromkovi\vc and   
                Jarkko Kari and   
                      Lila Kari   Some hierarchies for the communication
                                  complexity measures of cooperating
                                  grammar systems  . . . . . . . . . . . . 123--147
                 M. Jantzen and   
                    H. Petersen   Cancellation in context-free languages:
                                  enrichment by reduction  . . . . . . . . 149--170
             Katsushi Inoue and   
                  Akira Ito and   
                 Itsuo Takanami   On $1$-inkdot alternating Turing
                                  machines with small space  . . . . . . . 171--179
             Sergio De Agostino   P-complete problems in data compression  181--186
                   A. Del Lungo   Polyominoes defined by two vectors . . . 187--198

Theoretical Computer Science
Volume 127, Number 2, May 23, 1994

              Helen Cameron and   
                    Derick Wood   Balance in AVL trees and space cost of
                                  brother trees  . . . . . . . . . . . . . 199--228
                    Jarkko Kari   Rice's theorem for the limit sets of
                                  cellular automata  . . . . . . . . . . . 229--254
              Samir Khuller and   
        Stephen G. Mitchell and   
              Vijay V. Vazirani   On-line algorithms for weighted
                                  bipartite matching and stable marriages  255--267
                   Juha Honkala   On generalized DT$0$L systems and their
                                  fixed points . . . . . . . . . . . . . . 269--286
               Armando B. Matos   Periodic sets of integers  . . . . . . . 287--312
                  J. B. Yun\`es   Seven-state solutions to the Firing
                                  Squad Synchronization Problem  . . . . . 313--332
                E. Barcucci and   
                 R. Pinzani and   
                   R. Sprugnoli   The random generation of directed
                                  animals  . . . . . . . . . . . . . . . . 333--350
                Sanjay Jain and   
                    Arun Sharma   Program size restrictions in
                                  computational learning . . . . . . . . . 351--386
                A. H. Deutz and   
             A. Ehrenfeucht and   
                   G. Rozenberg   Hyperedge channels are abelian . . . . . 387--393
          Juraj Hromkovi\vc and   
       Claus-Dieter Jeschke and   
                Burkhard Monien   Note on optimal gossiping in some
                                  weak-connected graphs  . . . . . . . . . 395--402


Theoretical Computer Science
Volume 128, Number 1--2, June 06, 1994

             Yonatan Aumann and   
               Michael O. Rabin   Clock construction in fully asynchronous
                                  parallel systems and PRAM simulation . . 3--30
                   Tom Leighton   Methods for message routing in parallel
                                  machines . . . . . . . . . . . . . . . . 31--62
             J. Garofalakis and   
                P. Spirakis and   
                B. Tampakas and   
                    S. Rajsbaum   Tentative and definite distributed
                                  computations: an optimistic approach to
                                  network synchronization  . . . . . . . . 63--74
                Gilad Koren and   
                  Dennis Shasha   MOCA: a multiprocessor on-line
                                  competitive algorithm for real-time
                                  system scheduling  . . . . . . . . . . . 75--97
                Doron Peled and   
                  Mathai Joseph   A compositional framework for fault
                                  tolerance by specification
                                  transformation . . . . . . . . . . . . . 99--125
              Henk Schepers and   
                   Jozef Hooman   A trace-based compositional proof theory
                                  for fault tolerant distributed systems   127--157
           Padmanabhan Krishnan   A semantic characterisation for faults
                                  in replicated systems  . . . . . . . . . 159--177
            Hermann de Meer and   
          Kishor S. Trivedi and   
                  Mario Dal Cin   Guarded repair of dependable systems . . 179--210
        Vinay Sadananda Pai and   
 Alejandro A. Schäffer and   
                Peter J. Varman   Markov analysis of multiple-disk
                                  prefetching strategies for external
                                  merging  . . . . . . . . . . . . . . . . 211--239
             Jehoshua Bruck and   
              Robert Cypher and   
                  Ching-Tien Ho   Tolerating faults in a mesh with a row
                                  of spare nodes . . . . . . . . . . . . . 241--252


Theoretical Computer Science
Volume 129, Number 1, June 20, 1994

                Uri Abraham and   
               Menachem Magidor   On the mutual-exclusion problem --- a
                                  quest for minimal solutions  . . . . . . 1--38
              Hirofumi Yokouchi   $F$-semantics for type assignment
                                  systems  . . . . . . . . . . . . . . . . 39--77
          Jean-Louis L. Krivine   A general storage theorem for integers
                                  in call-by-name $\lambda$-calculus . . . 79--94
            Cheng-Chia Chen and   
                     I-Peng Lin   The computational complexity of the
                                  satisfiability of modal Horn clauses for
                                  modal propositional logics . . . . . . . 95--121
                    Jiawang Wei   Correctness of fixpoint transformations  123--142
              J. C. Shepherdson   The role of standardising apart in logic
                                  programming  . . . . . . . . . . . . . . 143--166
             Zoran Ognjanovi\'c   A tableau-like proof procedure for
                                  normal modal logics  . . . . . . . . . . 167--186
                      R. Banach   Regular relations and bicartesian
                                  squares  . . . . . . . . . . . . . . . . 187--192
                   Wenhui Zhang   Depth of proofs, depth of cut-formulas
                                  and complexity of cut formulas . . . . . 193--206

Theoretical Computer Science
Volume 129, Number 2, July 04, 1994

                A. H. Deutz and   
             A. Ehrenfeucht and   
                   G. Rozenberg   Clans and regions in $2$-structures  . . 207--262
         Jean-Paul Allouche and   
 Mireille Bousquet-Mélou   Canonical positions for the factors in
                                  paperfolding sequences . . . . . . . . . 263--278
             Bernard Delyon and   
                     Oded Maler   On the effects of noise and speed on
                                  computations . . . . . . . . . . . . . . 279--291
Joseph F. Jájá and   
                   Kwan Woo Ryu   An efficient parallel algorithm for the
                                  single function coarsest partition
                                  problem  . . . . . . . . . . . . . . . . 293--307
                     K. Ganesan   One-way functions and the isomorphism
                                  conjecture . . . . . . . . . . . . . . . 309--321
              Craig A. Rich and   
                  Giora Slutzki   The complexity of optimizing
                                  finite-state transducers . . . . . . . . 323--336
              Timo Knuutila and   
                 Magnus Steinby   The inference of tree languages from
                                  finite samples: an algebraic approach    337--367
                    S. Ferenczi   Tiling and local rank properties of the
                                  Morse sequence . . . . . . . . . . . . . 369--383
               Marion Scheepers   Variations on a game of Gale (II):
                                  Markov strategies  . . . . . . . . . . . 385--396
                   D. M. Yellin   An algorithm for dynamic subset and
                                  intersection testing . . . . . . . . . . 397--406
    Ömer E\vgecio\vglu and   
   Çetin Kaya Koç   Exponentiation using canonical recoding  407--417
                 M. Margenstern   Nonerasing Turing machines: a frontier
                                  between a decidable halting problem and
                                  universality . . . . . . . . . . . . . . 419--424


Theoretical Computer Science
Volume 130, Number 1, August 01, 1994

           Gerhard J. Woeginger   On-line scheduling of jobs with fixed
                                  start and end times  . . . . . . . . . . 5--16
             Rajeev Motwani and   
            Steven Phillips and   
                     Eric Torng   Nonclairvoyant scheduling  . . . . . . . 17--47
              Anja Feldmann and   
        Ji\vrí Sgall and   
                 Shang-Hua Teng   Dynamic scheduling on parallel machines  49--72
                 Yossi Azar and   
           Andrei Z. Broder and   
                 Anna R. Karlin   On-line load balancing . . . . . . . . . 73--84
                  Amos Fiat and   
                   Moty Ricklin   Competitive algorithms for the weighted
                                  server problem . . . . . . . . . . . . . 85--99
           Fabrizio d'Amore and   
            Vincenzo Liberatore   The list update problem and the
                                  retrieval of sets  . . . . . . . . . . . 101--123
       Bala Kalyanasundaram and   
                  Kirk R. Pruhs   Constructing competitive tours from
                                  local information  . . . . . . . . . . . 125--138
           John Hershberger and   
               Monika Rauch and   
                   Subhash Suri   Data structures for two-edge
                                  connectivity in planar graphs  . . . . . 139--161
Magnus M. Halldórsson and   
                  Mario Szegedy   Lower bounds for on-line graph coloring  163--174
                  Noga Alon and   
                  Gil Kalai and   
               Moty Ricklin and   
               Larry Stockmeyer   Lower bounds on the competitive ratio
                                  for mobile user tracking and distributed
                                  job scheduling . . . . . . . . . . . . . 175--201
        Peter Bro Miltersen and   
         Sairam Subramanian and   
       Jeffrey Scott Vitter and   
               Roberto Tamassia   Complexity models for incremental
                                  computation  . . . . . . . . . . . . . . 203--236

Theoretical Computer Science
Volume 130, Number 2, 1994

                       M. Nivat   Gödel's incompleteness theorem, by V. A.
                                  Uspensky . . . . . . . . . . . . . . . . 237
           Vladimir A. Uspensky   Gödel's incompleteness theorem  . . . . . 239--319


Theoretical Computer Science
Volume 131, Number 1, August 29, 1994

             Neil V. Murray and   
                 Erik Rosenthal   On the relative merits of path
                                  dissolution and the method of analytic
                                  tableaux . . . . . . . . . . . . . . . . 1--28
                      R. Banach   Term graph rewriting and garbage
                                  collection using opfibrations  . . . . . 29--94
               Kevin J. Compton   Stratified least fixpoint logic  . . . . 95--120
          Satoshi Kobayashi and   
                 Makoto Tatsuta   Realizability interpretation of
                                  generalized inductive definitions  . . . 121--138
                  Limor Fix and   
             Nissim Francez and   
                  Orna Grumberg   Program composition via unification  . . 139--179
                     Luca Aceto   GSOS and finite labelled transition
                                  systems  . . . . . . . . . . . . . . . . 181--195
           Philippe Mathieu and   
             Jean-Paul Delahaye   A kind of logical compilation for
                                  knowledge bases  . . . . . . . . . . . . 197--218
          David Scholefield and   
              Hussein Zedan and   
                      He Jifeng   A specification-oriented semantics for
                                  the refinement of real-time systems  . . 219--241

Theoretical Computer Science
Volume 131, Number 2, September 12, 1994

     Yael Etzion-Petruschka and   
                David Harel and   
                     Dale Myers   On the solvability of domino snake
                                  problems . . . . . . . . . . . . . . . . 243--269
            Craig C. Squier and   
             Friedrich Otto and   
                 Yuji Kobayashi   A finiteness condition for rewriting
                                  systems  . . . . . . . . . . . . . . . . 271--294
            Ramana M. Idury and   
     Alejandro A. Schäffer   Dynamic dictionary matching with failure
                                  functions  . . . . . . . . . . . . . . . 295--310
                 Ernst L. Leiss   Language equations over a one-letter
                                  alphabet with union, concatenation and
                                  star: a complete solution  . . . . . . . 311--330
         Hava T. Siegelmann and   
              Eduardo D. Sontag   Analog computation via neural networks   331--360
                Peter Eades and   
                 Sue Whitesides   Drawing graphs in two layers . . . . . . 361--374
                Dani\`ele Gardy   Join sizes, urn models, and normal
                                  limiting distributions . . . . . . . . . 375--414
                     J. Spencer   Randomization, derandomization and
                                  antirandomization: three games . . . . . 415--429
                    K. Eriksson   Reachability is decidable in the numbers
                                  game . . . . . . . . . . . . . . . . . . 431--439
              Dung T. Huynh and   
                        Lu Tian   A note on the complexity of deciding
                                  bisimilarity of normed unary processes   441--448
                  A. Bergey and   
                        R. Cori   On the orbits of the product of two
                                  permutations . . . . . . . . . . . . . . 449--461
                   C. Picouleau   Complexity of the Hamiltonian cycle in
                                  regular graph problem  . . . . . . . . . 463--473
                N. Anderson and   
                      D. Manley   A matrix extension of Winograd's inner
                                  product algorithm  . . . . . . . . . . . 475--477


Theoretical Computer Science
Volume 132, Number 1--2, September 26, 1994

          Philippe Flajolet and   
             Paul Zimmerman and   
             Bernard Van Cutsem   A calculus for the random generation of
                                  labelled combinatorial structures  . . . 1--35
            David W. Juedes and   
           James I. Lathrop and   
                   Jack H. Lutz   Computational depth and reducibility . . 37--70
                    E. L. Leiss   Unrestricted complementation in language
                                  equations over a one-letter alphabet . . 71--84
                  Changwook Kim   Retreat bounded picture languages  . . . 85--112
              Pascal Koiran and   
             Michel Cosnard and   
                     Max Garzon   Computability with low-dimensional
                                  dynamical systems  . . . . . . . . . . . 113--128
                      Lila Kari   On language equations with invertible
                                  operations . . . . . . . . . . . . . . . 129--150
                Paola Bonizzoni   Primitive $2$-structures with the
                                  $(n-2)$-property . . . . . . . . . . . . 151--178
            Giovanni Pighizzini   Asynchronous automata versus
                                  asynchronous cellular automata . . . . . 179--207
             A. Ehrenfeucht and   
                   R. McConnell   A $k$-structure generalization of the
                                  theory of $2$-structures . . . . . . . . 209--227
          Klaus Ambos-Spies and   
               Steven Homer and   
                Robert I. Soare   Minimal pairs and complete problems  . . 229--241
        Jean-Camille Birget and   
              Joseph B. Stephen   Formal languages defined by uniform
                                  substitutions  . . . . . . . . . . . . . 243--258
          Zsuzsanna Róka   One-way cellular automata on Cayley
                                  graphs . . . . . . . . . . . . . . . . . 259--290
          Alfredo De Santis and   
      Giovanni Di Crescenzo and   
              Guiseppe Persiano   The knowledge complexity of quadratic
                                  residuosity languages  . . . . . . . . . 291--317
          Juraj Hromkovi\vc and   
            Branislav Rovan and   
                 Anna Slobodova   Deterministic versus nondeterministic
                                  space in terms of synchronized
                                  alternating machines . . . . . . . . . . 319--336
                 R. Diestel and   
                      I. Leader   Domination games on infinite graphs  . . 337--345
        Jefferey A. Shufelt and   
               Hans J. Berliner   Generating Hamiltonian circuits without
                                  backtracking from errors . . . . . . . . 347--375
              Amir M. Ben-Amram   Unit-cost pointers versus
                                  logarithmic-cost addresses . . . . . . . 377--385
            Douglas Bridges and   
                Cristian Calude   On recursive bounds for the exceptional
                                  values in speed-up . . . . . . . . . . . 387--394
                Pierre Lescanne   On termination of one rule rewrite
                                  systems  . . . . . . . . . . . . . . . . 395--401
          Maxime Crochemore and   
                Wojciech Rytter   On two-dimensional pattern matching by
                                  optimal parallel algorithms  . . . . . . 403--414
                 J. Berstel and   
                   M. Pocchiola   Average cost of Duval's algorithm for
                                  generating Lyndon words  . . . . . . . . 415--425
                    Lucian Ilie   On a conjecture about slender
                                  context-free languages . . . . . . . . . 427--434
            Pavol \vDuri\vs and   
        José D. P. Rolim   A note on the density of oracle
                                  decreasing time-space complexity . . . . 435--444


Theoretical Computer Science
Volume 133, Number 1, October 11, 1994

                      Anonymous   Workshop on Continuous Algorithms and
                                  Complexity . . . . . . . . . . . . . . . ??
                  F. Cucker and   
                    M. Shub and   
                       S. Smale   Separation of complexity classes in
                                  Koiran's weak model  . . . . . . . . . . 3--14
                     T. Emerson   Relativizations of the P =? NP question
                                  over the reals (and other ordered rings) 15--22
               D. Yu. Grigoriev   Deviation theorems for solutions of
                                  differential equations and applications
                                  to lower bounds on parallel complexity
                                  of sigmoids  . . . . . . . . . . . . . . 23--33
                      P. Koiran   Computing over the reals with addition
                                  and order (complexity theory)  . . . . . 35--47
               Petr K\ocircurka   Regular unimodal systems and factors of
                                  finite automata  . . . . . . . . . . . . 49--64
            Gregorio Malajovich   On generalized Newton algorithms:
                                  quadratic convergence, path-following
                                  and error analysis . . . . . . . . . . . 65--84
                        K. Meer   On the complexity of quadratic
                                  programming in real number models of
                                  computation  . . . . . . . . . . . . . . 85--94
              Christian Michaux   P$\not=$NP over the nonstandard reals
                                  implies P$\not=$NP over $R$  . . . . . . 95--104
               J. Maurice Rojas   A convex geometric approach to counting
                                  the roots of a polynomial system . . . . 105--140
                    M. Shub and   
                       S. Smale   Complexity of Bezout's theorem V:
                                  Polynomial time  . . . . . . . . . . . . 141--164
             Jan Verschelde and   
                  Ann Haegemans   Homotopies for solving polynomial
                                  systems within a bounded domain  . . . . 165--185

Theoretical Computer Science
Volume 133, Number 2, October 24, 1994

          Anthony J. Bonner and   
                  Michael Kifer   An overview of transaction logic . . . . 205--265
              Fangqing Dong and   
          Laks V. S. Lakshmanan   Intuitionistic interpretation of
                                  deductive databases with incomplete
                                  information  . . . . . . . . . . . . . . 267--306
                   D. Kapur and   
                     X. Nie and   
                   D. R. Musser   An overview of the Tecton proof system   307--340
              Geetha Ramanathan   Refinement of events in the development
                                  of real-time distributed systems . . . . 341--359
                     Jiawei Han   Towards efficient induction mechanisms
                                  in database systems  . . . . . . . . . . 361--385
               Robert Godin and   
                 Rokia Missaoui   An incremental concept formation
                                  approach for learning from databases . . 387--419
                Fereidoon Sadri   Aggregate operations in the information
                                  source tracking method . . . . . . . . . 421--442


Theoretical Computer Science
Volume 134, Number 1, November 07, 1994

                      Anonymous   Second International Colloquium on
                                  Words, Languages and Combinatorics . . . ??
                 J. A. Anderson   Semiretracts of a free monoid  . . . . . 3--11
        Dani\`ele Beauquier and   
               Andreas Podelski   Rabin tree automata and finite monoids   13--25
      Agn\`es Bonnier-Rigny and   
                    Daniel Krob   A complete system of identities for
                                  one-letter rational expressions with
                                  multiplicities in the tropical semiring  27--50
           Fernando Botelho and   
                     Max Garzon   Boolean neural nets are observable . . . 51--61
        Renato M. Capocelli and   
              Luisa Gargano and   
                    Ugo Vaccaro   A fast algorithm for the unique
                                  decipherability of multivalued encodings 63--78
      Sini\vsa Crvenkovi\'c and   
Rozália Sz Madarász   On dynamic algebras  . . . . . . . . . . 79--86
                     V. Diekert   A partial trace semantics for Petri nets 87--105
          H. Jürgensen and   
                 K. Salomaa and   
                          S. Yu   Transducers and the decidability of
                                  independence in free monoids . . . . . . 107--117
    Alica Kelemenová and   
Erzsébet Csuhaj-Varjú   Languages of colonies  . . . . . . . . . 119--130
                       Teo Mora   An introduction to commutative and
                                  non-commutative Gröbner bases . . . . . . 131--173
             Friedrich Otto and   
              Paliath Narendran   Codes modulo finite monadic
                                  string-rewriting systems . . . . . . . . 175--188
               Norman R. Reilly   Bounds on the variety generated by
                                  completely regular syntactic monoids
                                  from finite prefix codes . . . . . . . . 189--208
                  J.-C. Spehner   A bijection between cliques in graphs
                                  and factorizations in free monoids . . . 209--223
                  Andreas Weber   Finite-valued distance automata  . . . . 225--251
                  Andreas Weber   Exponential upper and lower bounds for
                                  the order of a regular language  . . . . 253--262

Theoretical Computer Science
Volume 134, Number 2, November 21, 1994

                 J. Köbler   Locating P/poly optimally in the
                                  extended low hierarchy . . . . . . . . . 263--285
              Edward P. F. Chan   Testing satisfiability of a class of
                                  object-oriented conjunctive queries  . . 287--309
             Z. Fülöp   Undecidable properties of deterministic
                                  top-down tree transducers  . . . . . . . 311--328
           Michael Kaminski and   
                 Nissim Francez   Finite-memory automata . . . . . . . . . 329--363
   Ferucio Laurentiu Tiplea and   
               Cristian Ene and   
  Cecilia Magdalena Ionescu and   
             Octavian Procopiuc   Some decision problems for parallel
                                  communicating grammar systems  . . . . . 365--385
                      B. Durand   Inversion of 2D cellular automata: some
                                  complexity results . . . . . . . . . . . 387--401
                   T. Harju and   
            H. C. M. Kleijn and   
                 M. Latteux and   
                    A. Terlutte   Representation of rational functions
                                  with prefix and suffix codings . . . . . 403--413
                    Eric Remila   On the tiling of a torus with two bars   415--426
                      Louis Mak   Speedup of determinism by alternation
                                  for multidimensional Turing machines . . 427--453
     Franti\vsek Matú\vs   Stochastic independence, algebraic
                                  independence and abstract connectedness  455--471
                  Tao Jiang and   
                        Ming Li   Approximating shortest superstrings with
                                  constraints  . . . . . . . . . . . . . . 473--491
             Elias Dahlhaus and   
                Marek Karpinski   An efficient parallel algorithm for the
                                  minimal elimination ordering (MEO) of an
                                  arbitrary graph  . . . . . . . . . . . . 493--528
                 Laurent Alonso   Uniform generation of a Motzkin word . . 529--536
                  John Harrison   Morphic congruences and D$0$L languages  537--544
              Lance Fortnow and   
                John Rompel and   
                 Michael Sipser   On the power of multi-prover interactive
                                  protocols  . . . . . . . . . . . . . . . 545--557
                 Xunrang Gu and   
                    Yuzhang Zhu   Asymptotic optimal HEAPSORT algorithm    559--565


Theoretical Computer Science
Volume 135, Number 1, December 05, 1994

                      Anonymous   Mathematical Foundations of Programming
                                  Semantics  . . . . . . . . . . . . . . . ??
                Samson Abramsky   Proofs as processes  . . . . . . . . . . 5--9
                  G. Bellin and   
                    P. J. Scott   On the $\pi$-calculus and linear logic   11--65
            Didier Galmiche and   
                    Guy Perrier   On proof normalization in linear logic   67--110
              G. F. Mascari and   
                    M. Pedicini   Head linear reduction and pure proof net
                                  extraction . . . . . . . . . . . . . . . 111--137
                 P. Lincoln and   
                     A. Scedrov   First-order linear logic without
                                  modalities is NEXPTIME-hard  . . . . . . 139--153
            Patrick Lincoln and   
                Timothy Winkler   Constant-only multiplicative linear
                                  logic is NP-complete . . . . . . . . . . 155--169

Theoretical Computer Science
Volume 135, Number 2, December 12, 1994

             Christel Baier and   
      Mila E. Majster-Cederbaum   Denotational semantics in the cpo and
                                  metric approach  . . . . . . . . . . . . 171--220
              Hartmut Ehrig and   
       Martin Große-Rhode   Functorial theory of parameterized
                                  specifications in a general
                                  specification framework  . . . . . . . . 221--266
      Alexey L. Lastovetsky and   
           Sergey S. Gaissaryan   An algebraic approach to semantics of
                                  programming languages  . . . . . . . . . 267--288
              Felipe Bracho and   
                 Manfred Droste   Labelled domains and automata with
                                  concurrency  . . . . . . . . . . . . . . 289--318
             Pascal Manoury and   
               Marianne Simonot   Automatizing termination proofs of
                                  recursively defined functions  . . . . . 319--343
                    E. A. Scott   Weights for total division orderings on
                                  strings  . . . . . . . . . . . . . . . . 345--359
              Kunihiko Hiraishi   Some complexity results on transition
                                  systems and elementary net systems . . . 361--376
                  Jianan Li and   
              Ichiro Suzuki and   
             Masafumi Yamashita   Fair Petri nets and structural induction
                                  for rings of processes . . . . . . . . . 377--404
                Peter Trigg and   
           J. Roger Hindley and   
               Martin W. Bunder   Combinatory abstraction using $B$, $B'$
                                  and friends  . . . . . . . . . . . . . . 405--422
                       R. David   The Inf function in the system $F$ . . . 423--431


Theoretical Computer Science
Volume 136, Number 1, December 19, 1994

                P. T. Johnstone   Variations on the bagdomain theme  . . . 3--20
              Reinhold Heckmann   Stable power domains . . . . . . . . . . 21--56
               Adrian Fiech and   
                   Michael Huth   Algebraic domains of natural
                                  transformations  . . . . . . . . . . . . 57--78
              Austin Melton and   
  Bernd S. W. Schröder and   
             George E. Strecker   Lagois connections-a counterpart to
                                  Galois connections . . . . . . . . . . . 79--107
                Philip S. Mulry   Partial map classifiers and partial
                                  Cartesian closed categories  . . . . . . 109--123
                    Eike Ritter   Categorical abstract machines for
                                  higher-order typed lambda --- calculi    125--162
                Edmund Robinson   Parametricity as isomorphism . . . . . . 163--181
        Fairouz Kamareddine and   
                  Rob Nederpelt   A unified approach to type theory
                                  through a refined lambda --- calculus    183--216
                   Roy L. Crole   Computational adequacy of the FIX-logic  217--242
           Bettina Blaaberg and   
              Christian Clausen   Adequacy for a lazy functional language
                                  with recursive and polymorphic types . . 243--275
                  D. A. Wolfram   A semantics for $\lambda$Prolog  . . . . 277--289

Theoretical Computer Science
Volume 136, Number 2, December 29, 1994

                    Eric Remila   Recognition of graphs by automata  . . . 291--332
                 Enno Ohlebusch   On the modularity of termination of term
                                  rewriting systems  . . . . . . . . . . . 333--360
               Aldo de Luca and   
                Filippo Mignosi   Some combinatorial properties of
                                  Sturmian words . . . . . . . . . . . . . 361--385
                H. Senoussi and   
                      A. Saoudi   A quadtree algorithm for template
                                  matching on a pyramid computer . . . . . 387--417
             Vladimir Stetsenko   On almost bad Boolean bases  . . . . . . 419--469
                     M. Ito and   
                    G. Thierrin   Congruences, infix and cohesive prefix
                                  codes  . . . . . . . . . . . . . . . . . 471--485
               Elvira Mayordomo   Almost every set in exponential time is
                                  P-bi-immune  . . . . . . . . . . . . . . 487--506
              Marek Chrobak and   
                Wojciech Rytter   Two results on linear embeddings of
                                  complete binary trees  . . . . . . . . . 507--526
                 M. A. Kiwi and   
                R. Ndoundam and   
                M. Tchuente and   
                       E. Goles   No polynomial bound for the period of
                                  the parallel chip firing game on graphs  527--532


Theoretical Computer Science
Volume 141, Number 1--2, April 17, 1995

                    H. Petersen   A remark on a paper by A. B. Matos . . . 329--330


Theoretical Computer Science
Volume 182, Number 1--2, August 15, 1997

           Fernanda Botelho and   
                     Max Garzon   Erratum to ``Boolean neural nets are
                                  observable'' [Theoret. Comput. Sci. 134
                                  (1994) 51--61] . . . . . . . . . . . . . 257--257


Theoretical Computer Science
Volume 206, Number 1--2, October 06, 1998

                    Guy Perrier   Corrigendum to Galmiche's and Perrier's
                                  ``On proof normalization in linear
                                  logic'' [Theoret. Comput. Sci 135(1)
                                  (1994) 67--110]  . . . . . . . . . . . . 353--354


Theoretical Computer Science
Volume 234, Number 1--2, March 6, 2000

             Sergio De Agostino   Erratum to ``P-complete Problems in Data
                                  Compression'' [Theoret. Comput. Sci. 127
                                  (1994) 181--186] . . . . . . . . . . . . 325--326