Table of contents for issues of Theoretical Computer Science

Last update: Mon Mar 7 10:06:09 MST 2016                Valid HTML 3.2!

Volume 10, Number 1, January, 1980
Volume 10, Number 2, February, 1980
Volume 10, Number 3, March, 1980
Volume 11, Number 1, May, 1980
Volume 11, Number 2, June, 1980
Volume 11, Number 3, July, 1980
Volume 12, Number 1, September, 1980
Volume 12, Number 2, October, 1980
Volume 12, Number 3, November, 1980
Volume 13, Number 1, January, 1980
Volume 13, Number 2, February, 1981
Volume 13, Number 3, March, 1981
Volume 14, Number 1, April, 1981
Volume 14, Number 2, May, 1981
Volume 14, Number 3, June, 1981
Volume 15, Number 1, July, 1981
Volume 15, Number 2, August, 1981
Volume 15, Number 3, September, 1981
Volume 16, Number 1, October, 1981
Volume 16, Number 2, November, 1981
Volume 16, Number 3, December, 1981
Volume 17, Number 1, January, 1982
Volume 17, Number 2, February, 1982
Volume 17, Number 3, March, 1982
Volume 18, Number 1, April, 1982
Volume 18, Number 2, May, 1982
Volume 18, Number 3, June, 1982
Volume 19, Number 1, July, 1982
Volume 19, Number 2, August, 1982
Volume 19, Number 3, September, 1982
Volume 20, Number 1, March, 1982
Volume 20, Number 2, May, 1982
Volume 20, Number 3, July, 1982
Volume 21, Number 1, October, 1982
Volume 21, Number 2, November, 1982
Volume 21, Number 3, December, 1982
Volume 22, Number 1-2, January, 1983
Volume 22, Number 3, February, 1983
Volume 23, Number 1, March, 1983
Volume 23, Number 2, April, 1983
Volume 23, Number 3, May, 1983
Volume 24, Number 1, June, 1983
Volume 24, Number 2, July, 1983
Volume 24, Number 3, August, 1983
Volume 25, Number 1, January, 1983
Volume 25, Number 2, March, 1983
Volume 25, Number 3, July, 1983
Volume 26, Number 1-2, September, 1983
Volume 26, Number 3, October, 1983
Volume 27, Number 1-2, November, 1983
Volume 27, Number 3, December, 1983
Volume 28, Number 1-2, January, 1984
Volume 28, Number 3, February, 1984
Volume 29, Number 1-2, March, 1984
Volume 29, Number 3, April, 1984
Volume 30, Number 1, April, 1984
Volume 30, Number 2, August, 1984
Volume 30, Number 3, November, 1984
Volume 31, Number 1-2, May, 1984
Volume 31, Number 3, June, 1984
Volume 32, Number 1-2, July, 1984
Volume 32, Number 3, August, 1984
Volume 33, Number 1, September, 1984
Volume 33, Number 2-3, October, 1984
Volume 34, Number 1-2, November, 1984
Volume 34, Number 3, December, 1984


Theoretical Computer Science
Volume 10, Number 1, January, 1980

              C. P. Schnorr and   
             J. P. Van de Wiele   On the additive complexity of
                                  polynomials  . . . . . . . . . . . . . . 1--18
           J. A. Brzozowski and   
                       E. Leiss   On equations for regular languages,
                                  finite automata, and sequential networks 19--35
                     P. K\rurka   Applicability of a production in a
                                  categorical grammar  . . . . . . . . . . 37--44
             A. Ehrenfeucht and   
                   G. Rozenberg   Every two equivalent D0L systems have a
                                  regular true envelope  . . . . . . . . . 45--52
                W. Hartmann and   
                    P. Schuster   Multiplicative complexity of some
                                  rational functions . . . . . . . . . . . 53--61
                        S. Zaks   Lexicographic generation of ordered
                                  trees  . . . . . . . . . . . . . . . . . 63--82
                  C. P. Schnorr   A $3n$-lower bound on the network
                                  complexity of Boolean functions  . . . . 83--92
                      J. Biskup   Inferences of multivalued dependencies
                                  in fixed and undetermined universes  . . 93--105
                   H. Prodinger   On the interpolation of D0L-sequences    107--108

Theoretical Computer Science
Volume 10, Number 2, February, 1980

                 S. Fortune and   
                J. Hopcroft and   
                      J. Wyllie   The directed subgraph homeomorphism
                                  problem  . . . . . . . . . . . . . . . . 111--121
                  K. Lieberherr   P-optimal heuristics . . . . . . . . . . 123--131
                     E. Wiedmer   Computing with infinite objects  . . . . 133--155
                 A. de Luca and   
                     A. Restivo   On some properties of very pure codes    157--170
                     J. Staples   Computation on graph-like expressions    171--185
                    I. M. Havel   On branching and looping. I  . . . . . . 187--220

Theoretical Computer Science
Volume 10, Number 3, March, 1980

                       D. Kozen   Complexity of Boolean algebras . . . . . 221--247
                   R. Cohen and   
                        A. Gold   On the complexity of omega-type Turing
                                  acceptors  . . . . . . . . . . . . . . . 249--272
                    I. M. Havel   On branching and looping. II . . . . . . 273--295
                     J. Staples   Optimal evaluation of graph-like
                                  expressions  . . . . . . . . . . . . . . 297--316
                     K. N. King   Iteration theorems for families of
                                  strict deterministic languages . . . . . 317--333


Theoretical Computer Science
Volume 11, Number 1, May, 1980

               D. P. Dobkin and   
                    S. P. Reiss   The complexity of linear programming . . 1--18
                     J. Staples   Speeding up subtree replacement systems  39--47
                      L. Berman   The complexity of logical theories . . . 71--77
                  L. Kucera and   
                J. Nesetril and   
                       A. Pultr   Complexity of dimension three and some
                                  related edge-covering characteristics of
                                  graphs . . . . . . . . . . . . . . . . . 93--106
                        G. Hotz   A new invariant for context free
                                  languages  . . . . . . . . . . . . . . . 107--116

Theoretical Computer Science
Volume 11, Number 2, June, 1980

                      F. Harary   Graph theoretic models . . . . . . . . . 117--121
                  E. Borger and   
               H. Kleine Buning   The reachability problem for Petri nets
                                  and decision problems for Skolem
                                  arithmetic . . . . . . . . . . . . . . . 123--143
            A. L. Rosenberg and   
           L. J. Stockmeyer and   
                      L. Snyder   Uniform data encodings . . . . . . . . . 145--165
                   W. M. Beynon   On the structure of free finite state
                                  machines . . . . . . . . . . . . . . . . 167--180
                  A. Arnold and   
                       M. Nivat   Metric interpretations of infinite trees
                                  and semantics of nondeterministic
                                  recursive programs . . . . . . . . . . . 181--205
                     B. Bougaut   An explicit algorithm for PGCD research
                                  in certain principal rings between
                                  groups of numbers  . . . . . . . . . . . 207--220

Theoretical Computer Science
Volume 11, Number 3, July, 1980

          M. C. B. Hennessy and   
                 E. A. Ashcroft   A mathematical semantics for a
                                  nondeterministic typed lambda -calculus  227--245
                   H. Ehrig and   
                    B. K. Rosen   Parallelism and concurrency of graph
                                  manipulations  . . . . . . . . . . . . . 247--275
                       D. Kozen   Indexings of subrecursive classes  . . . 277--301
                    N. Blum and   
                    K. Mehlhorn   On the average number of rebalancing
                                  operations in weight-balanced trees  . . 303--320
                  J. Heintz and   
                   M. Sieveking   Lower bounds for polynomials with
                                  algebraic coefficients . . . . . . . . . 321--330
          J. von zur Gathen and   
                    V. Strassen   Some polynomials that are hard to
                                  compute  . . . . . . . . . . . . . . . . 331--335
                    A. B. Netto   There are infinitely many complete
                                  prefix codes of constant length $\ell
                                  (\ell\ge3)$  . . . . . . . . . . . . . . 337--339
                     M. Ben-Ari   Comments on `Tautology testing with a
                                  generalized matrix reduction method' . . 341


Theoretical Computer Science
Volume 12, Number 1, September, 1980

                    J. M. Jaffe   Efficient scheduling of tasks without
                                  full use of processor resources  . . . . 1--17
              N. Saheb-Djahromi   CPOs of measures for nondeterminism  . . 19--37
                   J. Winkowski   Behaviours of concurrent systems . . . . 39--60
                       D. Harel   Proving the correctness of regular
                                  deterministic programs: a unifying
                                  survey using dynamic logic . . . . . . . 61--81
                G. Ausiello and   
        A. Marchetti-Spaccamela   Toward a unified approach for the
                                  classification of NP-complete
                                  optimization problems  . . . . . . . . . 83--96
                      L. Monier   Evaluation and comparison of two
                                  efficient probabilistic primality
                                  testing algorithms . . . . . . . . . . . 97--108

Theoretical Computer Science
Volume 12, Number 2, October, 1980

                    P. W. Grant   Some more independence results in
                                  complexity theory  . . . . . . . . . . . 119--126
             A. Ehrenfeucht and   
                   G. Rozenberg   On ambiguity in E0L systems  . . . . . . 127--134
               H. A. Maurer and   
                 A. Salomaa and   
                        D. Wood   Synchronized E0L forms . . . . . . . . . 135--159
                     D. Angluin   On counting problems and the
                                  polynomial-time hierarchy  . . . . . . . 161--173
                   G. Cousineau   An algebraic definition for control
                                  structures . . . . . . . . . . . . . . . 175--192
                   J. C. Beatty   Two iteration theorems for the LL(k)
                                  languages  . . . . . . . . . . . . . . . 193--228

Theoretical Computer Science
Volume 12, Number 3, November, 1980

                      J. Tiuryn   Unique fixed points vs. least fixed
                                  points . . . . . . . . . . . . . . . . . 229--254
                  D. Dobkin and   
                    J. I. Munro   Determining the mode . . . . . . . . . . 255--263
                A. K. Joshi and   
                 L. S. Levy and   
                        K. Yueh   Local constraints in programming
                                  languages. I. Syntax . . . . . . . . . . 265--290
                    D. C. Oppen   Complexity, convexity and combinations
                                  of theories  . . . . . . . . . . . . . . 291--302
                  L. G. Valiant   Negation can be exponentially powerful   303--314
                J. I. Munro and   
                 M. S. Paterson   Selection and sorting with limited
                                  storage  . . . . . . . . . . . . . . . . 315--323
                  J. M. Boe and   
                 A. de Luca and   
                     A. Restivo   Minimal complete sets of words . . . . . 325--332
                    J. Gill and   
                    J. Hunt and   
                       J. Simon   Deterministic simulation of tape-bounded
                                  probabilistic Turing machine transducers 333--338
             A. Ehrenfeucht and   
                   G. Rozenberg   On a bound for the D0L sequence
                                  equivalence problem  . . . . . . . . . . 339--342


Theoretical Computer Science
Volume 13, Number 1, January, 1980

                    W. W. Wadge   An extensional treatment of dataflow
                                  deadlock . . . . . . . . . . . . . . . . 3--15
                N. A. Lynch and   
                  M. J. Fischer   On describing the behaviour and
                                  implementation of distributed systems    17--43
                      A. Pnueli   The temporal semantics of concurrent
                                  programs . . . . . . . . . . . . . . . . 45--60
      A. Maggiolo-Schettini and   
                   H. Wedde and   
                   J. Winkowski   Modeling a solution for a control
                                  problem in distributed systems by
                                  restrictions . . . . . . . . . . . . . . 61--83
                 M. Nielsen and   
                 G. Plotkin and   
                     G. Winskel   Petri nets, event structures and
                                  domains. I . . . . . . . . . . . . . . . 85--108
              H. J. Genrich and   
                  K. Lautenbach   System modelling with high-level Petri
                                  nets . . . . . . . . . . . . . . . . . . 109--136

Theoretical Computer Science
Volume 13, Number 2, February, 1981

                   H. Straubing   A generalization of the Schutzenberger
                                  product of finite monoids  . . . . . . . 137--150
                     J. E. Stoy   The congruence of two programming
                                  language definitions . . . . . . . . . . 151--174
                       D. Harel   On the total correctness of
                                  nondeterministic programs  . . . . . . . 175--192
                  J. H. Gallier   Nondeterministic flowchart programs with
                                  recursive procedures: semantics and
                                  correctness. I . . . . . . . . . . . . . 193--223
                 W. D. Goldfarb   The undecidability of the second-order
                                  unification problem  . . . . . . . . . . 225--230
                      W. Thomas   Remark on the star-height-problem  . . . 231--237

Theoretical Computer Science
Volume 13, Number 3, March, 1981

                  J. H. Gallier   Nondeterministic flowchart programs with
                                  recursive procedures: semantics and
                                  correctness. II  . . . . . . . . . . . . 239--270
                     E. Engeler   Generalized Galois theory and its
                                  application to complexity  . . . . . . . 271--293
               E. M. Gurari and   
                   O. H. Ibarra   The complexity of the equivalence
                                  problem for two characterizations of
                                  Presburger sets  . . . . . . . . . . . . 295--314
         F. Meyer Auf Der Heide   A comparison of two variations of a
                                  pebble game on graphs  . . . . . . . . . 315--322
                       E. Leiss   Succinct representation of regular
                                  languages by Boolean automata  . . . . . 323--330
                   Z. Galil and   
                    J. Seireras   Linear-time string-matching using only a
                                  fixed number of local storage locations  331--336


Theoretical Computer Science
Volume 14, Number 1, April, 1981

                        G. Gati   Some elements of a Galois theory of the
                                  structure and complexity of the tree
                                  automorphism problem . . . . . . . . . . 1--17
             J. Schulte Monting   Merging of 4 or 5 elements with $n$
                                  elements . . . . . . . . . . . . . . . . 19--37
               Y. Nishitani and   
                       N. Honda   The Firing Squad Synchronization problem
                                  for graphs . . . . . . . . . . . . . . . 39--61
                       E. Leiss   On generalized language equations  . . . 63--77
                   A. Rosenthal   Optimal algorithms for sensitivity
                                  analysis in associative multiplication
                                  problems . . . . . . . . . . . . . . . . 79--90
                     T. J. Long   On gamma -reducibility versus polynomial
                                  time many-one reducibility . . . . . . . 91--101
                       Z. Galil   On the theoretical efficiency of various
                                  network flow algorithms  . . . . . . . . 103--111
                   D. Kozen and   
                      R. Parikh   An elementary proof of the completeness
                                  of PDL . . . . . . . . . . . . . . . . . 113--118
                     M. Latteux   Concerning a lemma of substitution . . . 119--123

Theoretical Computer Science
Volume 14, Number 2, May, 1981

                     M. Jantzen   The power of synchronizing operations on
                                  strings  . . . . . . . . . . . . . . . . 127--154
                  J. H. Gallier   DPDA's in 'atomic normal form' and
                                  applications to equivalence problems . . 155--186
                   J. Beauquier   Substitution of semi-AFLs  . . . . . . . 187--193
                     D. Therien   Classification of finite monoids: The
                                  language approach  . . . . . . . . . . . 195--208

Theoretical Computer Science
Volume 14, Number 3, June, 1981

                 A. Maruoka and   
                  M. Kimura and   
                       N. Shoji   Pattern decomposition for tessellation
                                  automata . . . . . . . . . . . . . . . . 211--226
                  W. Bucher and   
               H. A. Maurer and   
                   K. Culik and   
                    D. Wotschke   Concise description of finite languages  227--246
                J. Stoklosa and   
                    W. Zakowski   Computations of $(\alpha,k)$-machines    247--265
               G. Rozenberg and   
                    R. Verraedt   On pure, terminal invariant and
                                  nonterminal invariant interpretations of
                                  E0L forms  . . . . . . . . . . . . . . . 267--288
                       S. Moran   General approximation algorithms for
                                  some arithmetical combinatorial problems 289--303
              G. Callegarin and   
                      G. Pacini   About the implementability and the power
                                  of equationally defined data
                                  abstractions . . . . . . . . . . . . . . 305--315
                      K. Jensen   Coloured Petri nets and the
                                  invariant-method . . . . . . . . . . . . 317--336
                      W. Bucher   A note on a problem in the theory of
                                  grammatical complexity . . . . . . . . . 337--344


Theoretical Computer Science
Volume 15, Number 1, July, 1981

                     G. Schmidt   Programs as partial graphs. I. Flow
                                  equivalence and correctness  . . . . . . 1--25
                     R. V. Book   Bounded query machines: on NP and PSPACE 27--39
                 R. V. Book and   
                    C. Wrathall   Bounded query machines: on NP() and
                                  NPQUERY()  . . . . . . . . . . . . . . . 41--50
                   T. Araki and   
                T. Kagimasa and   
                      N. Tokura   Relations of flow languages to Petri net
                                  languages  . . . . . . . . . . . . . . . 51--75
                      D. Lazard   Solution of algebraic equations systems  77--110

Theoretical Computer Science
Volume 15, Number 2, August, 1981

                 S. Heilbrunner   A parsing automata approach to LR theory 117--157
                     G. Schmidt   Programs as partial graphs. II.
                                  Recursion  . . . . . . . . . . . . . . . 159--179
            L. H. Landweber and   
               R. J. Lipton and   
                E. L. Robertson   On the structure of sets in NP and other
                                  complexity classes . . . . . . . . . . . 181--200
                   A. Alder and   
                    V. Strassen   On the algorithmic complexity of
                                  associative algebras . . . . . . . . . . 201--211
                 G. Germano and   
          A. Maggiolo-Schettini   Sequence recursiveness without
                                  cylindrification and limited register
                                  machines . . . . . . . . . . . . . . . . 213--221

Theoretical Computer Science
Volume 15, Number 3, September, 1981

             J. W. Thatcher and   
               E. G. Wagner and   
                   J. B. Wright   More on advice on structuring compilers
                                  and proving them correct . . . . . . . . 223--249
                     A. Paz and   
                       S. Moran   Non deterministic polynomial
                                  optimization problems and their
                                  approximations . . . . . . . . . . . . . 251--277
         E. W. Leggett, Jr. and   
                    D. J. Moore   Optimization problems and the polynomial
                                  hierarchy  . . . . . . . . . . . . . . . 279--289
              H. P. Katseff and   
                      M. Sipser   Several results in program size
                                  complexity . . . . . . . . . . . . . . . 291--309
                     M. C. Loui   A space bound for one-tape
                                  multidimensional Turing machines . . . . 311--320
                C. Benzaken and   
                      S. Foldes   Complexity of graph embeddability
                                  problems . . . . . . . . . . . . . . . . 321--328
                    R. Stratman   On the existence of closed terms in the
                                  type lambda calculus. II:
                                  transformations of unification problems  329--338


Theoretical Computer Science
Volume 16, Number 1, October, 1981

               K. Weihrauch and   
                   U. Schreiber   Embedding metric spaces into cpos  . . . 5--24
             A. Ehrenfeucht and   
                   G. Rozenberg   On the subword complexity of square-free
                                  D0L languages  . . . . . . . . . . . . . 25--32
                  S. Takasu and   
                    S. Kawabata   A logical basis for programming
                                  methodology  . . . . . . . . . . . . . . 43--60
                     M. Jantzen   On a special monoid with a single
                                  defining relation  . . . . . . . . . . . 61--73
                       J. Simon   On tape-bounded probabilistic Turing
                                  machine acceptors  . . . . . . . . . . . 75--91
                 M. G. Main and   
                   D. B. Benson   Free upper regular bands . . . . . . . . 93--98
                  K. Lieberherr   Uniform complexity and digital
                                  signatures . . . . . . . . . . . . . . . 99--110

Theoretical Computer Science
Volume 16, Number 2, November, 1981

                     Ren-ji Tao   On the computational power of automata
                                  with time or space bounded by
                                  Ackermann's or superexponential
                                  functions  . . . . . . . . . . . . . . . 115--148
                      J. Pittle   On LLP(k) grammars and languages . . . . 149--175
                G. Galbiati and   
                  M. J. Eischer   On the complexity of $2$-output Boolean
                                  networks . . . . . . . . . . . . . . . . 177--185
                K.-J. Raiha and   
                     E. Ukkonen   The shortest common supersequence
                                  problem over binary alphabet is
                                  NP-complete  . . . . . . . . . . . . . . 187--198
                     L. Csirmaz   Programs and program verifications in a
                                  general setting  . . . . . . . . . . . . 199--210
               V. L. Nguyen and   
                   J. L. Lassez   A dual problem to least fixed points . . 211--221
                 R. V. Book and   
               C. P. O'Dunlaing   Testing for the Church--Rosser property  223--229
               I. L. Carter and   
                       R. Eagin   A note on the existence of continuous
                                  functionals  . . . . . . . . . . . . . . 231--235

Theoretical Computer Science
Volume 16, Number 3, December, 1981

            H. C. M. Kleijn and   
                   G. Rozenberg   Context-free restrictions on selective
                                  rewriting  . . . . . . . . . . . . . . . 237--269
                     K. Lam and   
                  M. K. Siu and   
                       C. T. Yu   A generalized counter scheme . . . . . . 271--278
             W. A. Burkhard and   
              M. L. Fredman and   
                 D. J. Kleitman   Inherent complexity trade-offs for range
                                  query problems . . . . . . . . . . . . . 279--290
                  J. Albert and   
                      L. Wegner   Languages with homomorphic replacements  291--305
                U. I. Gupta and   
                  D. T. Lee and   
               J. W. Pruitt and   
                     C. K. Wong   Record allocation for minimizing seek
                                  delay  . . . . . . . . . . . . . . . . . 307--319
                  F. Berman and   
                    M. Paterson   Propositional Dynamic Logic is weaker
                                  without tests  . . . . . . . . . . . . . 321--328
            H. Edelsbrunner and   
                   H. A. Maurer   A space-optimal solution of general
                                  region location  . . . . . . . . . . . . 329--336


Theoretical Computer Science
Volume 17, Number 1, January, 1982

                M. Blattner and   
                    S. Ginsburg   Position-restricted grammar forms and
                                  grammars . . . . . . . . . . . . . . . . 1--27
                       E. Welzl   Color-families are dense . . . . . . . . 29--41
                     E. Ekkonen   Structure preserving elimination of null
                                  productions from context-free grammars   43--54
               E. M. Gurari and   
                   O. H. Ibarra   Some simplified undecidable and NP-hard
                                  problems for simple programs . . . . . . 55--73
                   J. Hartmanis   A note on natural complete sets and
                                  Godel numberings . . . . . . . . . . . . 75--89
                    M. M. Syslo   The subgraph isomorphism problem for
                                  outerplanar graphs . . . . . . . . . . . 91--97
                   M. Karpinski   Decidability of `Skolem matrix emptiness
                                  problem' entails constructability of
                                  exact regular expression . . . . . . . . 99--102
                  W. D. Fellner   On minimal graphs  . . . . . . . . . . . 103--110

Theoretical Computer Science
Volume 17, Number 2, February, 1982

             J. A. Bergstra and   
                  J. Tiuryn and   
                   J. V. Tucker   Floyd's principle, correctness theories
                                  and program equivalence  . . . . . . . . 113--149
                 D. Lehmann and   
                     A. Pasztor   Epis need not be dense . . . . . . . . . 151--161
               B. Courcelle and   
         P. Franchi-Zannettacci   Attribute grammars and recursive program
                                  schemes. I . . . . . . . . . . . . . . . 163--191
                 H. Andreka and   
                  I. Nemeti and   
                        I. Sain   A complete logic for reasoning about
                                  programs via nonstandard model theory. I 193--212
               R. D. Dutton and   
                  R. C. Brigham   The complexity of a multiprocessor task
                                  assignment problem without deadlines . . 213--216
              J. C. Shepherdson   Graph theoretic characterization of
                                  G-schemes and TL-schemes . . . . . . . . 217--228
                  C. Squier and   
                    C. Wrathall   A note on representations of a certain
                                  monoid . . . . . . . . . . . . . . . . . 229--231

Theoretical Computer Science
Volume 17, Number 3, March, 1982

               B. Courcelle and   
         P. Franchi-Zannettacci   Attribute grammars and recursive program
                                  schemes. II  . . . . . . . . . . . . . . 235--257
                 H. Andreka and   
                  I. Nemeti and   
                        I. Sain   A complete logic for reasoning about
                                  programs via nonstandard model theory.
                                  II . . . . . . . . . . . . . . . . . . . 259--278
                  N. Dershowitz   Orderings for term-rewriting systems . . 279--301
             J. A. Bergstra and   
                   J. V. Tucker   Some natural structures which fail to
                                  possess a sound and decidable Hoare-like
                                  logic for their while-programs . . . . . 303--315
                   F. Sadri and   
                   J. D. Ullman   The theory of functional and template
                                  dependencies . . . . . . . . . . . . . . 317--331
             R. K. Shyamasundar   On a characterization of pushdown
                                  permuters  . . . . . . . . . . . . . . . 333--341
                      I. Nemeti   Every free algebra in the variety
                                  generated by the representable dynamic
                                  algebras is separable and representable  343--347


Theoretical Computer Science
Volume 18, Number 1, April, 1982

                        C. Pair   Abstract data types and algebraic
                                  semantics of programming languages . . . 1--31
               J. Goldstine and   
                J. K. Price and   
                    D. Wotschke   A pushdown automaton or a context-free
                                  grammar-which is more economical?  . . . 33--40
                   A. P. Ershov   Mixed computation: potential
                                  applications and problems for study  . . 41--67
                     J. Hagauer   On form-equivalence of deterministic
                                  pure grammar forms . . . . . . . . . . . 69--87
                   G. Schnitger   A family of graphs with expensive
                                  depth-reduction  . . . . . . . . . . . . 89--93
                    U. Schoning   A uniform approach to obtain diagonal
                                  sets in complexity classes . . . . . . . 95--103
                       M. Furer   The complexity of Presburger arithmetic
                                  with bounded quantifier alternation
                                  depth  . . . . . . . . . . . . . . . . . 105--111

Theoretical Computer Science
Volume 18, Number 2, May, 1982

                 J. Berstel and   
                  C. Reutenauer   Recognizable formal power series on
                                  trees  . . . . . . . . . . . . . . . . . 115--148
                        E. Best   Adequacy properties of path programs . . 149--171
                   F. Boussinot   Proposition of denotational semantics
                                  for processing networks with a 'fair
                                  merge' operator  . . . . . . . . . . . . 173--206
                    K. Uchimura   Properties of structure generating
                                  functions of automata and their
                                  applications for linear systems  . . . . 207--220
                  M. Crochemore   Sharp characterizations of squarefree
                                  morphisms  . . . . . . . . . . . . . . . 221--226

Theoretical Computer Science
Volume 18, Number 3, June, 1982

                     J. Sifakis   A unified approach for studying the
                                  properties of transition systems . . . . 227--258
                     D. Leivant   Unprovability of theorems of complexity
                                  theory in weak number theories . . . . . 259--268
               K. Culik, II and   
                       T. Harju   Dominoes over a free monoid  . . . . . . 279--300
                A. R. Meyer and   
                   K. Winklmann   Expressing program looping in regular
                                  dynamic logic  . . . . . . . . . . . . . 301--323
                     R. V. Book   When is a monoid a group? The
                                  Church--Rosser case is tractible . . . . 325--331
                     S. Istrail   Generalization of the Ginsburg-Rice
                                  Schutzenberger fixed-point theorem for
                                  context-sensitive and
                                  recursive-enumerable languages . . . . . 333--341


Theoretical Computer Science
Volume 19, Number 1, July, 1982

                    Y. Perl and   
                        S. Zaks   On the complexity of edge labelings for
                                  trees  . . . . . . . . . . . . . . . . . 1--16
               O. H. Ibarra and   
            B. S. Leininger and   
                       S. Moran   On the complexity of simple arithmetic
                                  expressions  . . . . . . . . . . . . . . 17--28
               K. Culik, II and   
                     A. Salomaa   On infinite words obtained by iterating
                                  morphisms  . . . . . . . . . . . . . . . 29--38
               D. Yu. Grigor'ev   Additive complexity in directed
                                  computations . . . . . . . . . . . . . . 39--67
                       R. Sethi   Pebble games for studying storage
                                  sharing  . . . . . . . . . . . . . . . . 69--84

Theoretical Computer Science
Volume 19, Number 2, August, 1982

                    P. Padawitz   Graph grammars and operational semantics 117--141
                   J. Paredaens   A universal formalism to express
                                  decompositions, functional dependencies
                                  and other constraints in a relational
                                  database . . . . . . . . . . . . . . . . 143--160
                H. R. Lewis and   
            C. H. Papadimitriou   Symmetric space-bounded computation  . . 161--187
         G. N. Frederickson and   
                       J. Ja'Ja   On the relationship between the
                                  biconnectivity augmentation and
                                  traveling salesman problems  . . . . . . 189--201
                   A. C.-C. Yao   On the time-space tradeoff for sorting
                                  with linear queries  . . . . . . . . . . 203--218
                   O. H. Ibarra   2DST mappings on languages and related
                                  problems . . . . . . . . . . . . . . . . 219--227

Theoretical Computer Science
Volume 19, Number 3, September, 1982

                 R. V. Book and   
                 M. Jantzen and   
                    C. Wrathall   Monadic Thue systems . . . . . . . . . . 231--251
                 K. R. Reischuk   A fast implementation of a
                                  multidimensional storage into a tree
                                  storage  . . . . . . . . . . . . . . . . 253--266
                  P. Atzeni and   
                G. Ausiello and   
                  C. Batini and   
                   M. Moscarini   Inclusion and equivalence between
                                  relational database schemata . . . . . . 267--285
                   A. L. Selman   Reductions on NP and P-selective sets    287--304
                  H. Szwerinski   Time-optimal solution of the
                                  firing-squad-synchronization-problem for
                                  $n$-dimensional rectangles with the
                                  general at an arbitrary position . . . . 305--320
                        M. Snir   Comparisons between linear functions can
                                  help . . . . . . . . . . . . . . . . . . 321--330
                  B. R. Hodgson   On direct products of automaton
                                  decidable theories . . . . . . . . . . . 331--335
                     N. Megiddo   Is binary encoding appropriate for the
                                  problem-language relationship? . . . . . 337--341


Theoretical Computer Science
Volume 20, Number 1, March, 1982

                        M. Wand   Specifications, models, and
                                  implementations of data abstractions . . 3--32

Theoretical Computer Science
Volume 20, Number 2, May, 1982

                        W. Damm   The IO- and OI-hierarchies (tree
                                  language theory) . . . . . . . . . . . . 95--207

Theoretical Computer Science
Volume 20, Number 3, July, 1982

                   H. Ehrig and   
             H.-J. Kreowski and   
                    B. Mahr and   
                    P. Padawitz   Algebraic implementation of abstract
                                  data types . . . . . . . . . . . . . . . 209--263
                   G. Berry and   
                   P. L. Curien   Sequential algorithms on concrete data
                                  structures . . . . . . . . . . . . . . . 265--321
                   K.-I. Ko and   
                    H. Friedman   Computational complexity of real
                                  functions  . . . . . . . . . . . . . . . 323--352


Theoretical Computer Science
Volume 21, Number 1, October, 1982

                     T. J. Long   Strong nondeterministic polynomial-time
                                  reducibilities . . . . . . . . . . . . . 1--25
                      S. Miyano   Two-way deterministic multi-weak-counter
                                  machines . . . . . . . . . . . . . . . . 27--37
                   P. Duris and   
                       Z. Galil   Fooling a two way automaton, or, one
                                  pushdown store is better than one
                                  counter for two way machines . . . . . . 39--53
                D. Janssens and   
                   G. Rozenberg   Graph grammars with
                                  neighbourhood-controlled embedding . . . 55--74
             A. Ehrenfeucht and   
                   G. Rozenberg   Representation theorems using D0S
                                  language . . . . . . . . . . . . . . . . 75--90
                    R. Cori and   
                       A. Machi   Construction of maps with prescribed
                                  automorphism group . . . . . . . . . . . 91--98
               X. Berenguer and   
                    J. Diaz and   
                   L. H. Harper   A solution of the Sperner-Erd\Hos
                                  problem  . . . . . . . . . . . . . . . . 99--103
         L. M. Goldschlager and   
                 R. A. Shaw and   
                     J. Staples   The maximum flow problem is log space
                                  complete for P . . . . . . . . . . . . . 105--111

Theoretical Computer Science
Volume 21, Number 2, November, 1982

             A. Ehrenfeucht and   
               J. Karhumaki and   
                   G. Rozenberg   The (generalized) Post Correspondence
                                  Problem with lists consisting of two
                                  words is decidable . . . . . . . . . . . 119--144
                     M. C. Loui   Simulations among multidimensional
                                  Turing machines  . . . . . . . . . . . . 145--161
                     W. Ainhirn   Marvellous interpretations differ little
                                  but decisively from ordinary
                                  interpretations of EOL forms . . . . . . 163--178
                  B. S. Chlebus   On the computational complexity of
                                  satisfiability in propositional logics
                                  of programs  . . . . . . . . . . . . . . 179--212
                     I. Wegener   Boolean functions whose monotone
                                  complexity is of size $n^2\log n$  . . . 213--224
                 S. W. Margolis   The syntactic transformation semigroup
                                  of a language generated by a finite
                                  biprefix code  . . . . . . . . . . . . . 225--230
                     L. Csirmaz   Determinateness of program equivalence
                                  over Peano axioms  . . . . . . . . . . . 231--235

Theoretical Computer Science
Volume 21, Number 3, December, 1982

                  B. Monien and   
               I. H. Sudborough   On eliminating nondeterminism from
                                  Turing machines which use less than
                                  logarithm worktape space . . . . . . . . 237--253
                 C. F. Kent and   
                  B. R. Hodgson   An arithmetical characterization of NP   255--267
             J. A. Bergstra and   
                 J.-J. C. Meyer   On the elimination of iteration
                                  quantifiers in a fragment of algorithmic
                                  logic  . . . . . . . . . . . . . . . . . 269--279
                   K. Indermark   On rational definitions in complete
                                  algebras without rank  . . . . . . . . . 281--313
                   J. Winkowski   An algebraic description of system
                                  behaviours . . . . . . . . . . . . . . . 315--340
                     S. Istrail   Some remarks on nonalgebraic adherences  341--349
                     P. K\rurka   Ergodic languages  . . . . . . . . . . . 351--355
                    T. Head and   
                   J. Wilkinson   Finite DOL languages and codes . . . . . 357--361


Theoretical Computer Science
Volume 22, Number 1-2, January, 1983

                     R. Hindley   The completeness theorem for typing
                                  lambda -terms  . . . . . . . . . . . . . 1--17
                        M. Sato   Theory of symbolic expressions. I  . . . 19--55
                   J. Pittl and   
                     A. Yehudai   Constructing a realtime deterministic
                                  pushdown automaton from a grammar  . . . 57--69
                        P. Gacs   On the relation between descriptional
                                  complexity and algorithmic probability   71--93
                   W. Kuich and   
                  F. J. Urbanek   Infinite linear systems and one counter
                                  languages  . . . . . . . . . . . . . . . 95--126
                     R. Hindley   Curry's type-rules are complete with
                                  respect to the $F$-semantics too . . . . 127--133
                  G. Boudol and   
                        L. Kott   Recursion induction principle revisited  135--173
                     M. Ito and   
               K. Taniguchi and   
                      T. Kasami   Membership problem for embedded
                                  multivalued dependencies under some
                                  restricted conditions  . . . . . . . . . 175--194
              G. W. Wasilkowski   Any iteration for polynomial equations
                                  using linear information has infinite
                                  complexity . . . . . . . . . . . . . . . 195--208
                  D. T. Lee and   
                  C. L. Liu and   
                     C. K. Wong   ($g_0, g_1,\ldots{},g_k$)-trees and
                                  unary 0L systems . . . . . . . . . . . . 209--217
                     M. Steinby   Systolic trees and systolic language
                                  recognition by tree automata . . . . . . 219--232

Theoretical Computer Science
Volume 22, Number 3, February, 1983

                     G. Lev and   
                  L. G. Valiant   Size bounds for superconcentrators . . . 233--251
                   M. Takahashi   Nest sets and relativized closure
                                  properties . . . . . . . . . . . . . . . 253--264
             J. A. Bergstra and   
                   J. V. Tucker   Hoare's logic and Peano's arithmetic . . 265--284
                  A. Lempel and   
                G. Seroussi and   
                    S. Winograd   On the complexity of multiplication in
                                  finite fields  . . . . . . . . . . . . . 285--296
              A. Apostolico and   
                F. P. Preparata   Optimal off-line detection of
                                  repetitions in a string  . . . . . . . . 297--315
                   W. Bauer and   
                    V. Strassen   The complexity of partial derivatives    317--330
                   H. A. Maurer   L codes and number systems . . . . . . . 331--346


Theoretical Computer Science
Volume 23, Number 1, March, 1983

            Chuang-jie Tang and   
                    Yi-li Zhang   The limited regular languages  . . . . . 1--10
               A. Jankowski and   
                     C. Rauszer   Logical foundation approach to users'
                                  domain restriction in data bases . . . . 11--36
                A. Nakamura and   
                         H. Ono   Pictures of functions and their
                                  acceptability by automata  . . . . . . . 37--48
                 S. Heilbrunner   A metatheorem for undecidable properties
                                  of formal languages and its application
                                  to LRR and LLR grammars and languages    49--68
              F.-J. Brandenburg   Uniformly growing $k$-th power-free
                                  homorphisms  . . . . . . . . . . . . . . 69--82
                    T. Head and   
                G. Thierrin and   
                   J. Wilkinson   DOL schemes and the periodicity of
                                  string embeddings  . . . . . . . . . . . 83--89
                     A. Nijholt   On satisfying the LL-iteration theorem   91--94
              Tat-hung Chan and   
                   O. H. Ibarra   On the finite-valuedness problem for
                                  sequential machines  . . . . . . . . . . 95--101
                  P. V. Ramanan   A counterexample to Shyamasundar's
                                  characterization of pushdown permuters   103--105

Theoretical Computer Science
Volume 23, Number 2, April, 1983

                     E. Gelenbe   Stationary deterministic flows in
                                  discrete systems. I (computer
                                  performance modelling) . . . . . . . . . 107--127
                      E. Tomita   A direct branching algorithm for
                                  checking equivalence of strict
                                  deterministic vs. LL(k) grammars . . . . 129--154
                   G. S. Eisman   On depth in EDTOL languages  . . . . . . 155--169
                   G. Lotti and   
                      F. Romani   On the asymptotic complexity of
                                  rectangular matrix multiplication  . . . 171--185
                  R. J. R. Back   A continuous semantics for unbounded
                                  nondeterminism . . . . . . . . . . . . . 187--210
                    J. Finn and   
                  K. Lieberherr   Primality testing and factoring  . . . . 211--215
               M. Takahashi and   
                    H. Yamasaki   A note on omega-regular languages  . . . 217--225

Theoretical Computer Science
Volume 23, Number 3, May, 1983

                   K. Culik and   
                  J. Gruska and   
                     A. Salomaa   On a family of L languages resulting for
                                  systolic tree automata . . . . . . . . . 231--242
                  T. Etzion and   
                       M. Yoeli   Super-nets and their hierarchy . . . . . 243--272
    A. Marchetti-Spaccamela and   
                      M. Prtasi   The largest tree in a random graph . . . 273--286
                      R. Freund   Real functions and numbers defined by
                                  Turing machines  . . . . . . . . . . . . 287--304
                  D. Gordon and   
                      E. Shamir   Computation of recursive functionals
                                  using minimal initial segments . . . . . 305--315
                      H. Volger   Turing machines with linear alternation,
                                  theories of bounded concatenation and
                                  the decision problem of first order
                                  theories . . . . . . . . . . . . . . . . 333--337
                 C. O'Dunglaing   Undecidable questions related to
                                  Church--Rosser Thue systems  . . . . . . 339--345


Theoretical Computer Science
Volume 24, Number 1, June, 1983

                       H. Wedde   An iterative and starvation-free
                                  solution for a general class of
                                  distributed control problems based on
                                  interaction primitives . . . . . . . . . 1--20
                 A. de Luca and   
                 A. Restivo and   
                      S. Salemi   On the centers of a language . . . . . . 21--34
               O. H. Ibarra and   
                   S. Moran and   
                   L. E. Rosier   On the control power of integer division 35--52
             J. J. Grefenstette   Stability in L systems . . . . . . . . . 53--71
                  D. A. Schmidt   Approximation properties of abstract
                                  data types . . . . . . . . . . . . . . . 73--94
                    R. P. Daley   On the error correcting power of
                                  pluralism in BC-type inductive inference 95--104
                    O. Watanabe   The time-precision tradeoff problem on
                                  on-line probabilistic Turing machines    105--117

Theoretical Computer Science
Volume 24, Number 2, July, 1983

                B. Chazelle and   
                      L. Monier   Unbounded hardware is equivalent to
                                  deterministic Turing machines  . . . . . 123--130
               N. Soundararajan   Correctness proofs of CSP programs . . . 131--141
              K. K. Nambiar and   
           T. Radhakrishnan and   
                  V. G. Tikekar   Representation of functional
                                  dependencies in relational databases
                                  using linear graphs  . . . . . . . . . . 143--159
                A. Nakamura and   
                      K. Aizawa   On a relationship between graph
                                  L-systems and picture languages  . . . . 161--177
                    M. Toda and   
                   K. Inoue and   
                    I. Takanami   Two-dimensional pattern matching by
                                  two-dimensional on-line tessellation
                                  acceptors  . . . . . . . . . . . . . . . 179--194
               R. Siromoney and   
                    R. Dare and   
              K. G. Subramanian   Infinite arrays and infinite
                                  computations . . . . . . . . . . . . . . 195--205
                  A. Bagchi and   
                     A. Mahanti   Admissible heuristic search in AND/OR
                                  graphs . . . . . . . . . . . . . . . . . 207--219

Theoretical Computer Science
Volume 24, Number 3, August, 1983

                   J. A. Storer   Toward an abstract theory of data
                                  compression  . . . . . . . . . . . . . . 221--237
                      J. Heintz   Definability and fast quantifier
                                  elimination in algebraically closed
                                  fields . . . . . . . . . . . . . . . . . 239--277
                   S. Homer and   
                       W. Maass   Oracle-dependent properties of the
                                  lattice of NP sets . . . . . . . . . . . 279--289
             U. V. Vazirani and   
                 V. V. Vazirani   A natural encoding scheme proved
                                  probabilistic polynomial complete  . . . 291--300
                     R. V. Book   Decidable sentences of Church--Rosser
                                  congruences  . . . . . . . . . . . . . . 301--312
                   O. H. Ibarra   On some decision questions concerning
                                  pushdown machines  . . . . . . . . . . . 313--322
              P. C. Fischer and   
                  J. H. Jou and   
                     D.-M. Tsou   Succinctness in dependency systems . . . 323--329
                   K. Inoue and   
                I. Takanami and   
                   H. Taniguchi   A relationship between two-dimensional
                                  finite automata and three-way
                                  tape-bounded two-dimensional Turing
                                  machines . . . . . . . . . . . . . . . . 331--336
                  E.-R. Olderog   On the notion of expressiveness and the
                                  rule of adaptation . . . . . . . . . . . 337--347


Theoretical Computer Science
Volume 25, Number 1, January, 1983

                   A. J. Kfoury   Definability by programs in first-order
                                  structures . . . . . . . . . . . . . . . 1--66
                      E. Nelson   Iterative algebras . . . . . . . . . . . 67--94

Theoretical Computer Science
Volume 25, Number 2, March, 1983

                   B. Courcelle   Fundamental properties of infinite trees 95--169
                  C. O'Dunlaing   Infinite regular Thue systems  . . . . . 171--192
                    J. Case and   
                       C. Smith   Comparison of identification criteria
                                  for machine inductive inference  . . . . 193--120

Theoretical Computer Science
Volume 25, Number 3, July, 1983

                      L. Priese   Automata and concurrency . . . . . . . . 221--265
                      R. Milner   Calculi for synchrony and asynchrony . . 267--310
                        R. Valk   Infinite behaviour of Petri nets . . . . 311--341


Theoretical Computer Science
Volume 26, Number 1-2, September, 1983

                   E. B. Kinber   The inclusion problem for some classes
                                  of deterministic multitape automata  . . 1--24
               I. H. Sudborough   Bandwidth constraints on problems
                                  complete for polynomial time . . . . . . 25--52
            J. W. de Bakker and   
            J.-J. Ch. Meyer and   
                   J. I. Zucker   On infinite computations in denotational
                                  semantics  . . . . . . . . . . . . . . . 53--82
                 S. Istrail and   
                   C. Masalagiu   Nivat's processing systems: decision
                                  problems related to protection and
                                  synchronization  . . . . . . . . . . . . 83--103
            E. C. R. Hehner and   
                 C. A. R. Hoare   A more complete model of communicating
                                  processes  . . . . . . . . . . . . . . . 105--120
                  E. A. Emerson   Alternative semantics for temporal
                                  logics . . . . . . . . . . . . . . . . . 121--130
               K. Weihrauch and   
                     G. Schafer   Admissible representations of effective
                                  CPO's  . . . . . . . . . . . . . . . . . 131--147
                S. Ginsburg and   
                        R. Hull   Order dependency in the relational model 149--195
               O. H. Ibarra and   
                   L. E. Rosier   Simple programming languages and
                                  restricted classes of Turing machines    197--220
                      A. Arnold   Rational omega-languages are
                                  non-ambiguous  . . . . . . . . . . . . . 221--223
                     V. Rajlich   Determinism in parallel systems  . . . . 225--231
                  W. Bucher and   
                     J. Hagauer   It is decidable whether a regular
                                  language is pure context-free  . . . . . 233--241

Theoretical Computer Science
Volume 26, Number 3, October, 1983

                S. Ginsburg and   
                        R. Hull   Characterizations for functional
                                  dependency and Boyce-Codd normal form
                                  families . . . . . . . . . . . . . . . . 243--286
                      C. K. Yap   Some consequences of non-uniform
                                  conditions on uniform classes  . . . . . 287--300
               G. Rozenberg and   
                    R. Verraedt   Subset languages of Petri nets. I. The
                                  relationship to string languages and
                                  normal forms . . . . . . . . . . . . . . 301--326
                         S. Zak   A Turing machine time hierarchy  . . . . 327--333
                   J. Hartmanis   On Godel speed-up and succinctness of
                                  language representations . . . . . . . . 335--342
                 J. Staples and   
                   V. L. Nguyen   Computing the behaviour of asynchronous
                                  processes  . . . . . . . . . . . . . . . 343--353


Theoretical Computer Science
Volume 27, Number 1-2, November, 1983

                 H. B. Hunt and   
              D. J. Rosenkrantz   The complexity of monadic recursion
                                  schemes: executability problems, nesting
                                  depth, and applications  . . . . . . . . 3--38
                T. Kamimura and   
                        A. Tang   Algebraic relations and presentations    39--60
                   K. Inoue and   
                I. Takanami and   
                   H. Taniguchi   Two-dimensional alternating Turing
                                  machines . . . . . . . . . . . . . . . . 61--83
               G. Rozenberg and   
                    R. Verraedt   Subset languages of Petri nets. II.
                                  Closure properties . . . . . . . . . . . 85--108
                    M. B. Smyth   The largest Cartesian closed category of
                                  domains  . . . . . . . . . . . . . . . . 109--119
                   P. Duris and   
                   J. Hromkovic   One-way simple multihead finite automata
                                  are not closed under concatenation . . . 121--125
              J. Y. Halpern and   
                     J. H. Reif   The propositional dynamic logic of
                                  deterministic, well-structured programs  127--165
               H.-D. Ehrich and   
                      U. Lipeck   Algebraic domain equations . . . . . . . 167--196
         A. P. Stolboushkin and   
                 M. A. Taitslin   The comparison of the expressive power
                                  of first-order dynamic logics  . . . . . 197--209
             S. Bozapalidis and   
         O. Louscou-Bozapalidou   The rank of a formal tree power series   211--215
                     A. Maruoka   Open maps for tessellation automata  . . 217--224
                  J. Adamek and   
                      E. Nelson   Separately continuous algebras . . . . . 225--231

Theoretical Computer Science
Volume 27, Number 3, December, 1983

               D. P. Dobkin and   
              D. G. Kirkpatrick   Fast detection of polyhedral
                                  intersection . . . . . . . . . . . . . . 241--253
                   H. Ehrig and   
                 H.-J. Kreowski   Compatibility of parameter passing and
                                  implementation of parameterized data
                                  types  . . . . . . . . . . . . . . . . . 255--286
                        N. Blum   More on the power of chain rules in
                                  context-free grammars  . . . . . . . . . 287--295
                  R. D. Tennent   Semantics of interference control  . . . 297--310
             A. Ehrenfeucht and   
                D. Haussler and   
                   G. Rozenberg   On regularity of context-free languages  311--332
                       D. Kozen   Results on the propositional mu-calculus 333--354


Theoretical Computer Science
Volume 28, Number 1-2, January, 1984

                        W. Paul   On heads versus tapes  . . . . . . . . . 1--12
                 J. Maluszynski   Towards a programming language based on
                                  the notion of two-level grammar  . . . . 13--43
                   H. Ehrig and   
             H.-J. Kreowski and   
                J. Thatcher and   
                  E. Wagner and   
                      J. Wright   Parameter passing in algebraic
                                  specification languages  . . . . . . . . 45--81
                      K. R. Apt   Ten years of Hoares logic: a survey. II.
                                  Nondeterminism . . . . . . . . . . . . . 83--109
                R. Wiehagen and   
               R. Freivalds and   
                   E. B. Kinber   On the power of probabilistic strategies
                                  in inductive inference . . . . . . . . . 111--133
                        D. Bini   On commutativity and approximation . . . 135--150
      S. Ronchi Della Rocca and   
                     B. Venneri   Principal type schemes for an extended
                                  type theory  . . . . . . . . . . . . . . 151--169
               C. Fernandez and   
              P. S. Thiagarajan   D-continuous causal nets: a model of
                                  non-sequential processes . . . . . . . . 171--196
             A. Ehrenfeucht and   
               G. Rozenberg and   
                    R. Verraedt   On inherently ambiguous E0L languages    197--214
             J. A. Bergstra and   
                   J. V. Tucker   Hoare's logic for programming languages
                                  with two data types  . . . . . . . . . . 215--221
                 T. Kanaoka and   
                      S. Tomita   The decomposition of stochastic systems  223--233
                  J. R. Hindley   Coppo-Dezani types do not correspond to
                                  propositional logic  . . . . . . . . . . 235--236

Theoretical Computer Science
Volume 28, Number 3, February, 1984

                  P. T. Cox and   
               T. Pietrzykowski   A complete, nonredundant algorithm for
                                  reversed Skolemization . . . . . . . . . 239--261
             D. Kirkpatrick and   
                      S. Reisch   Upper bounds for sorting integers on
                                  random access machines . . . . . . . . . 263--276
                  W. Bucher and   
               H. A. Maurer and   
                       K. Culik   Context-free complexity of finite
                                  languages  . . . . . . . . . . . . . . . 277--285
             F. Parisi-Presicce   Iterative factor algebras and induced
                                  metrics  . . . . . . . . . . . . . . . . 287--298
                  A. Kelemenova   Complexity of normal form grammars . . . 299--314
               K. Kobayashi and   
               M. Takahashi and   
                    H. Yamasaki   Characterization of omega-regular
                                  languages by first-order formulas  . . . 315--327
                      D. Perrin   Completing biprefix codes  . . . . . . . 329--336
                        N. Blum   A Boolean function requiring $3n$
                                  network size . . . . . . . . . . . . . . 337--345


Theoretical Computer Science
Volume 29, Number 1-2, March, 1984

                J. F. Traub and   
          G. W. Wasilkowski and   
                H. Wozniakowski   Average case optimality for linear
                                  problems . . . . . . . . . . . . . . . . 1--25
                E. Orlowska and   
                      Z. Pawlak   Representation of nondeterministic
                                  information  . . . . . . . . . . . . . . 27--39
               G. Rozenberg and   
                    R. Verraedt   On simulation and propagating E0L forms  41--48
                 A. S. Fraenkel   Wythoff games, continued fractions,
                                  cedar trees and Fibonacci searches . . . 49--73
             G. N. Frederickson   Recursively rotated orders and implicit
                                  data structures: a lower bound . . . . . 75--85
                     R. Janicki   Nets, sequential components and
                                  concurrency relations  . . . . . . . . . 87--121
               O. H. Ibarra and   
                      S. M. Kim   Characterizations and computational
                                  complexity of systolic trellis automata  123--153
                T. Kamimura and   
                        A. Tang   Effectively given spaces . . . . . . . . 155--166
               J.-L. Lassez and   
                    M. J. Maher   Closures and fairness in the semantics
                                  of programming logic . . . . . . . . . . 167--184
                 E. Fachini and   
                      M. Napoli   Hierarchies of primitive recursive
                                  wordsequence functions: comparisons and
                                  decision problems  . . . . . . . . . . . 185--227

Theoretical Computer Science
Volume 29, Number 3, April, 1984

                   T. Elrad and   
                     N. Francez   A weakest precondition semantics for
                                  communicating processes  . . . . . . . . 231--250
             M. Venturini Zilli   Reduction graphs in the lambda calculus  251--275
                    D. H. Potts   Remarks on an example of Jantzen . . . . 277--284
                   J. Karhumaki   The Ehrenfeucht conjecture: a
                                  compactness claim for finitely generated
                                  free monoids . . . . . . . . . . . . . . 285--308
                       M. Coppo   Completeness of type assignment in
                                  continuous lambda models . . . . . . . . 309--324
                   G. S. Eisman   On the ratio of growth functions in
                                  EDT0L languages  . . . . . . . . . . . . 325--349


Theoretical Computer Science
Volume 30, Number 1, April, 1984

             J. A. Bergstra and   
                     J. W. Klop   Proving program inclusion using Hoare's
                                  logic  . . . . . . . . . . . . . . . . . 1--48
                  E.-R. Olderog   Correctness of programs with PASCAL-like
                                  procedures without global variables  . . 49--90
                  D. Austry and   
                      G. Boudol   Algebra of processes and synchronisation 91--131
                   R. de Simone   On MEIJE and SCCS: infinite sum
                                  operators vs. non-guarded definitions    133--138

Theoretical Computer Science
Volume 30, Number 2, August, 1984

                  H. A. Klaeren   A constructive method for abstract
                                  algebraic software specification . . . . 139--204
          J. P. Braquelaire and   
                   B. Courcelle   The solutions of two star-height
                                  problems for regular trees . . . . . . . 205--239

Theoretical Computer Science
Volume 30, Number 3, November, 1984

              H. J. Genrich and   
              P. S. Thiagarajan   A theory of bipolar synchronization
                                  schemes  . . . . . . . . . . . . . . . . 241--318
               L. Denenberg and   
                    H. R. Lewis   The complexity of the satisfiability
                                  problem for Krom formulas  . . . . . . . 319--341


Theoretical Computer Science
Volume 31, Number 1-2, May, 1984

                H. Yamasaki and   
                   M. Takahashi   Generalized parenthesis languages and
                                  minimization of their parenthesis parts  1--11
               N. Soundararajan   A proof technique for parallel programs  13--29
                   K. Bruce and   
                       G. Longo   On combinatory algebras and their
                                  expansions . . . . . . . . . . . . . . . 31--40
                    U. Schoning   Minimal pairs for P  . . . . . . . . . . 41--48
                    B. Mahr and   
                 J. A. Makowsky   Characterizing specification languages
                                  which admit initial semantics  . . . . . 49--59
                     J. Honkala   Bases and ambiguity of number systems    61--71
                   D. F. Escrig   A characterization of Plotkin's order in
                                  powerdomains, and some of its properties 73--82
                   R. De Simone   Infinitary and mixed product languages   83--100
                       Ker-I Ko   Reducibilities on real numbers . . . . . 101--123
                 D. A. Plaisted   New NP-hard and NP-complete polynomial
                                  and integer divisibility problems  . . . 125--138
                        T. Head   Adherences of D0L languages  . . . . . . 139--149
                   M. Mezghiche   A new C beta -reduction in combinatory
                                  logic  . . . . . . . . . . . . . . . . . 151--162
               P. Narendran and   
                  R. McNaughton   The undecidability of the preperfectness
                                  of Thue systems  . . . . . . . . . . . . 165--174
               J. A. Goguen and   
                 R. M. Burstall   Some fundamental algebraic tools for the
                                  semantics of computation. I. Comma
                                  categories, colimits, signatures and
                                  theories . . . . . . . . . . . . . . . . 175--209
             A. Ehrenfeucht and   
                 M. G. Main and   
                   G. Rozenberg   Restrictions on NLC graph grammars . . . 211--223

Theoretical Computer Science
Volume 31, Number 3, June, 1984

                    K. Uchimura   Truncations of infinite matrices and
                                  algebraic series associated with some CF
                                  grammars . . . . . . . . . . . . . . . . 227--261
               J. A. Goguen and   
                 R. M. Burstall   Some fundamental algebraic tools for the
                                  semantics of computation. II. Signed and
                                  abstract theories  . . . . . . . . . . . 263--295
                     H. Alaiwan   Equivalance of infinite behavior of
                                  finite automata  . . . . . . . . . . . . 297--306
                    H. Yamasaki   Normal Petri nets  . . . . . . . . . . . 307--315
                  M. Oyamaguchi   Some results on subclass containment
                                  problems for special classes of DPDAs
                                  related to nonsingular machines  . . . . 317--335
             J. M. Autebert and   
               J. Beauquier and   
                 L. Boasson and   
                 G. Senizergues   Remarks on parenthesis languages . . . . 337--349


Theoretical Computer Science
Volume 32, Number 1-2, July, 1984

                   J. C. Raoult   On graph rewritings  . . . . . . . . . . 1--24
                 N. Francez and   
                 D. Lehmann and   
                      A. Pnueli   A linear-history semantics for languages
                                  for distributed programming  . . . . . . 25--46
                   J. Duske and   
                   R. Parchmann   Linear indexed languages . . . . . . . . 47--60
                J. Avenhaus and   
                    K. Madlener   The Nielsen reduction and P-complete
                                  problems in free groups  . . . . . . . . 61--76
                 F. Y. Chin and   
               P. Kossowski and   
                      S. C. Loh   Efficient inference control for range
                                  SUM queries  . . . . . . . . . . . . . . 77--86
                      E. Tomita   An extended direct branching algorithm
                                  for checking equivalence of
                                  deterministic pushdown automata  . . . . 87--120
               E. Astesiano and   
                       G. Costa   Distributive semantics for
                                  nondeterministic typed lambda ---
                                  calculi  . . . . . . . . . . . . . . . . 121--156
                     U. Vishkin   A parallel-design
                                  distributed-implementation (PDDI)
                                  general-purpose computer . . . . . . . . 157--172
                     D. McAloon   Petri nets and large finite sets . . . . 173--183
                       D. Maier   Connections in acyclic hypergraphs . . . 185--199
                     T. E. Hall   Biprefix codes, inverse semigroups and
                                  syntactic monoids of injective automata  201--213
                    R. Meshulam   A geometric construction of a
                                  superconcentrator of depth 2 . . . . . . 215--219
                     J. W. Hong   A tradeoff theorem for space and
                                  reversal . . . . . . . . . . . . . . . . 221--224

Theoretical Computer Science
Volume 32, Number 3, August, 1984

               K. Culik, II and   
                          S. Yu   Iterative tree automata  . . . . . . . . 227--247
                        F. Otto   Finite complete rewriting systems for
                                  the Jantzen monoid and the Greendlinger
                                  group  . . . . . . . . . . . . . . . . . 249--260
                       V. Niemi   The undecidability of form equivalence
                                  for context-free and E0L forms . . . . . 261--277
                J. Avenhaus and   
                    K. Madlener   On the complexity of intersection and
                                  conjugacy problems in free groups  . . . 279--295
                 J. Ketonen and   
                   R. Weyhrauch   A decidable fragment of predicate
                                  calculus (theorem proving) . . . . . . . 297--307
                N. G. de Bruijn   Some machines defined by directed graphs 309--319
                  S. Miyano and   
                     T. Hayashi   Alternating finite automata on
                                  omega-words  . . . . . . . . . . . . . . 321--330
                     L. Staiger   Projection lemmas for omega-languages    331--337
                   G. Jacob and   
                  C. Reutenauer   On formal power series defined by
                                  infinite linear systems  . . . . . . . . 339--340


Theoretical Computer Science
Volume 33, Number 1, September, 1984

                      Anonymous   Second Conference on Foundations of
                                  Software Technology and Theoretical
                                  Computer Science . . . . . . . . . . . . ??
               R. Siromoney and   
          K. G. Subramanian and   
                     V. R. Dare   Infinite arrays and controlled
                                  deterministic table 0L array systems . . 3--11
                 M. Jantzen and   
                      M. Kudlek   Homomorphic images of sentential form
                                  languages defined by semi-Thue systems   13--43
               E. Astesiano and   
                       E. Zucca   Parametric channels via label
                                  expressions in CCS . . . . . . . . . . . 45--63
                  K. R. Apt and   
                  A. Pnueli and   
                       J. Stavi   Fair termination revisited-with delay    65--84
               B. Ravikumar and   
               K. B. Lakshmanan   Coping with known patterns of lies in a
                                  search game  . . . . . . . . . . . . . . 85--94
                      P. Dybjer   Some results on the deductive structure
                                  of join dependencies . . . . . . . . . . 95--105
            C. E. Veni Madhavan   Secondary attribute retrieval using tree
                                  data structures  . . . . . . . . . . . . 107--116
                     V. Ya. Pan   The techniques of trilinear aggregating
                                  and the recent progress in the
                                  asymptotic acceleration of matrix
                                  operations . . . . . . . . . . . . . . . 117--138

Theoretical Computer Science
Volume 33, Number 2-3, October, 1984

                    M. Broy and   
                 M. Wirsing and   
                        C. Pair   A systematic study of models of abstract
                                  data types . . . . . . . . . . . . . . . 139--174
                      S. Kaplan   Conditional rewrite rules  . . . . . . . 175--193
                        E. Fehr   Expressive power of typed and type-free
                                  programming languages  . . . . . . . . . 195--238
                    Y. Maon and   
                     A. Yehudai   On test sets for checking morphism
                                  equivalence on languages with fair
                                  distribution of letters  . . . . . . . . 239--240
                        F. Otto   Some undecidability results for
                                  non-monadic Church--Rosser Thue systems  261--278
               N. Soundararajan   Denotational semantics of CSP  . . . . . 279--304
                    D. T. Huynh   Deciding the inequivalence of
                                  context-free grammars with $1$- letter
                                  terminal alphabet is
                                  ${\Sigma}_2^p$-complete  . . . . . . . . 305--326
                   T. Harju and   
                       M. Linna   The equations $ h(w) = w^n $ in binary
                                  alphabets  . . . . . . . . . . . . . . . 327--329
                  D. Perrin and   
                      P. Schupp   On the one-relator monoids which are
                                  groups . . . . . . . . . . . . . . . . . 331--334
           D. Girault-Beauquier   Bilimits of recognisable languages . . . 335--342


Theoretical Computer Science
Volume 34, Number 1-2, November, 1984

                    J. Nesetril   Some nonstandard Ramsey like
                                  applications . . . . . . . . . . . . . . 3--15
               J. Hartmanis and   
                       Y. Yesha   Computation times of NP sets of
                                  different densities  . . . . . . . . . . 17--32
                     G. Winskel   Synchronization trees  . . . . . . . . . 33--82
               R. de Nicola and   
              M. C. B. Hennessy   Testing equivalences for processes
                                  (concurrent programming) . . . . . . . . 83--133
            J. W. de Bakker and   
             J. A. Bergstra and   
                 J. W. Klop and   
                 J.-J. C. Meyer   Linear time and branching time semantics
                                  for recursion with merge (parallel
                                  programming languages) . . . . . . . . . 135--156
               P. M. B. Vitanyi   On the simulation of many storage heads
                                  by one . . . . . . . . . . . . . . . . . 157--168
               M.-P. Delest and   
                     G. Viennot   Algebraic languages and polyomino
                                  enumeration  . . . . . . . . . . . . . . 169--206
                  A. K. Lenstra   Factoring multivariate integral
                                  polynomials  . . . . . . . . . . . . . . 207--213
                   S. Cohen and   
                 D. Lehmann and   
                      A. Pnueli   Symmetric and economical solutions to
                                  the mutual exclusion problem in a
                                  distributed system . . . . . . . . . . . 215--225
                    T. Sato and   
                      H. Tamaki   Enumeration of success patterns in logic
                                  programs (PROLOG)  . . . . . . . . . . . 227--240

Theoretical Computer Science
Volume 34, Number 3, December, 1984

                M. Clerbout and   
                     M. Latteux   Partial commutations and faithful
                                  rational transductions . . . . . . . . . 241--254
                 Y. Itzhaik and   
                     A. Yehudai   New families of non real time DPDAs and
                                  their decidability results . . . . . . . 255--274
                T. Kamimura and   
                        A. Tang   Total objects of domains . . . . . . . . 275--288
                 M. Gogolla and   
                 K. Drosten and   
                  U. Lipeck and   
                   H.-D. Ehrich   Algebraic and operational semantics of
                                  specifications allowing exceptions and
                                  errors . . . . . . . . . . . . . . . . . 289--313
                     M. Ito and   
                 M. Iwasaki and   
               K. Taniguchi and   
                      T. Kasami   Membership problems for data
                                  dependencies in relational expressions   315--335
                    U. Schoning   On small generators  . . . . . . . . . . 337--341
               F. Bancilhon and   
                     P. Richard   A sound and complete axiomatization of
                                  embedded cross dependencies  . . . . . . 343--350