Table of contents for issues of Theoretical Computer Science

Last update: Sat Feb 8 17:05:19 MST 2014                Valid HTML 3.2!

Volume 1, Number 1, June, 1975
Volume 1, Number 2, December, 1975
Volume 1, Number 3, February, 1976
Volume 1, Number 4, April, 1976
Volume 2, Number 1, June, 1976
Volume 2, Number 2, 1976
Volume 2, Number 3, September, 1976
Volume 3, Number 1, October, 1976
Volume 3, Number 2, November, 1976
Volume 3, Number 3, December, 1976
Volume 4, Number 1, February, 1977
Volume 4, Number 2, April, 1977
Volume 4, Number 3, June, 1977
Volume 5, Number 1, August, 1977
Volume 5, Number 2, October, 1977
Volume 5, Number 3, December, 1977
Volume 6, Number 1, February, 1978
Volume 6, Number 2, April, 1978
Volume 6, Number 3, June, 1978
Volume 7, Number 1, August, 1978
Volume 7, Number 2, October, 1978
Volume 7, Number 3, December, 1978
Volume 8, Number 1, February, 1979
Volume 8, Number 2, April, 1979
Volume 8, Number 3, June, 1979
Volume 9, Number 1, July, 1979
Volume 9, Number 2, August, 1979


Theoretical Computer Science
Volume 1, Number 1, June, 1975

                   A. Schonhage   A lower bound for the length of addition
                                  chains . . . . . . . . . . . . . . . . . 1--12
                 M. S. Paterson   Complexity of monotone networks for
                                  Boolean matrix product . . . . . . . . . 13--20
                    V. Strassen   The computational complexity of symbolic
                                  differentiation of interpolating
                                  polynomials  . . . . . . . . . . . . . . 21--25
                     G. P. Huet   A unification algorithm for typed lambda
                                  -calculus  . . . . . . . . . . . . . . . 27--57
             A. Ehrenfeucht and   
                  K. P. Lee and   
                   G. Rozenberg   Subword complexities of various classes
                                  of deterministic developmental languages
                                  without interactions . . . . . . . . . . 59--75
                   A. Reedy and   
                  W. J. Savitch   The Turing degree of the inherent
                                  ambiguity problem for context-free
                                  languages  . . . . . . . . . . . . . . . 77--91

Theoretical Computer Science
Volume 1, Number 2, December, 1975

                     A. Restivo   A combinatorial property of codes having
                                  finite synchronization delay . . . . . . 95--101
               R. E. Ladner and   
                N. A. Lynch and   
                   A. L. Selman   A comparison of polynomial time
                                  reducibilities . . . . . . . . . . . . . 103--123
                  G. D. Plotkin   Call-by-name, call-by-value and the
                                  lambda-calculus  . . . . . . . . . . . . 125--159
               L. H. Harper and   
                W. N. Hsieh and   
                   J. E. Savage   A class of Boolean functions with linear
                                  combinational complexity . . . . . . . . 161--133
                F. P. Preparata   A fast stable sorting algorithm with
                                  absolutely minimum storage . . . . . . . 185--190

Theoretical Computer Science
Volume 1, Number 3, February, 1976

                        R. Moll   An operator embedding theorem for
                                  complexity classes of recursive
                                  functions  . . . . . . . . . . . . . . . 193--198
                 J. Leeuwen and   
                        D. Wood   A decomposition theorem for
                                  hyper-algebraic extensions of language
                                  families . . . . . . . . . . . . . . . . 199--214
                     R. V. Book   Translational lemmas, polynomial time,
                                  and $(\log n)^j$ --- space . . . . . . . 215--216
                    M. Mignotte   Algorithms relating to the decomposition
                                  of polynomials . . . . . . . . . . . . . 227--235
                M. R. Garey and   
                  D. S. Johnson   Some simplified NP-complete graph
                                  problems . . . . . . . . . . . . . . . . 237--267

Theoretical Computer Science
Volume 1, Number 4, April, 1976

                 S. A. Greibach   Remarks on the complexity of
                                  nondeterministic counter languages . . . 269--288
                  C. P. Schnorr   The combinational complexity of
                                  equivalence  . . . . . . . . . . . . . . 289--295
                 E. P. Friedman   The inclusion problem for simple
                                  languages  . . . . . . . . . . . . . . . 297--316
                   J. Karhumaki   Two theorems concerning recognizable
                                  N-subsets of sigma * . . . . . . . . . . 317--323
             A. Ehrenfeucht and   
               G. Rozenberg and   
                       S. Skyum   A relationship between ET0L and EDT0L
                                  languages  . . . . . . . . . . . . . . . 325--330
                   W. Marek and   
                      Z. Pawlak   Information storage and retrieval
                                  systems: mathematical foundations  . . . 331--354
                  M. L. Fredman   How good is the information theory bound
                                  in sorting?  . . . . . . . . . . . . . . 355--361


Theoretical Computer Science
Volume 2, Number 1, June, 1976

                      I. Meznik   On some subclasses of the class of
                                  generable languages  . . . . . . . . . . 1--7
                  J. Engelfriet   Surface tree languages and parallel
                                  derivation trees . . . . . . . . . . . . 9--27
                S. Ginsburg and   
               J. Goldstine and   
                    S. Greibach   Some uniformly erasable families of
                                  languages  . . . . . . . . . . . . . . . 29--44
                  G. J. Chaitin   Information-theoretic characterizations
                                  of recursive infinite strings  . . . . . 45--48
               P. M. B. Vitanyi   Deterministic Lindenmayer languages,
                                  nonterminals and homomorphisms . . . . . 49--71
                     M. Machtey   Minimal pairs of polynomial degrees with
                                  subexponential complexity  . . . . . . . 73--76
                        M. Hack   The quality problem for vector addition
                                  systems is undecidable . . . . . . . . . 77--95
                     J.-J. Levy   An algebraic interpretation of the
                                  lambda beta K-calculus; and an
                                  application of a labelled
                                  lambda-calculus  . . . . . . . . . . . . 97--114
               G. T. Herman and   
                      A. Walker   On the stability of some biological
                                  schemes with cellular interactions . . . 115--130

Theoretical Computer Science
Volume 2, Number 2, 1976

                    H. Egli and   
                R. L. Constable   Computability concepts for programming
                                  language semantics . . . . . . . . . . . 133--145
             J. I. Seiferas and   
                  R. McNaughton   Regularity-preserving relations  . . . . 147--154
                J. W. De Bakker   Least fixed points revisited . . . . . . 155--181
                    B. K. Rosen   Correctness of parallel programs: the
                                  Church--Rosser approach  . . . . . . . . 183--207
                     L. Boasson   Algebraic languages, iterative pairs and
                                  rational transductions . . . . . . . . . 209--223
             M. B. Trakhtenbrot   Relationships between classes of
                                  monotonic functions  . . . . . . . . . . 228--247
                      B. Vilfan   Lower bounds for the size of expressions
                                  for certain functions in $d$-ary logic   249--269

Theoretical Computer Science
Volume 2, Number 3, September, 1976

               O. H. Ibarra and   
                S. K. Sahni and   
                      C. E. Kim   Finite automata with multiplication  . . 271--294
              F. N. Springsteel   On the pre-AFL of (log n) space and
                                  related families of languages  . . . . . 295--304
                  C. P. Schnorr   A lower bound on the number of additions
                                  in monotone computations . . . . . . . . 305--315
                    M. Soittola   Positive rational sequences  . . . . . . 317--322
          M. Dezani-Ciancaglini   Characterization of normal forms
                                  possessing inverse in the
                                  $\lambda-\beta-\eta$-calculus  . . . . . 323--337
                    S. Even and   
                   R. E. Tarjan   Computing an $st$-numbering  . . . . . . 339--344
                   E. Minicozzi   Some natural properties of
                                  strong-identification in inductive
                                  inference  . . . . . . . . . . . . . . . 345--360
                 H. B. Hunt and   
          D. J. Rosenkrantz and   
                T. G. Szymanski   The covering problem for linear
                                  context-free grammars  . . . . . . . . . 361--382
                     W. J. Paul   Realizing Boolean functions on disjoint
                                  sets of variables  . . . . . . . . . . . 383--396
             M. S. Paterson and   
                  L. G. Valiant   Circuit size is nonlinear in depth . . . 397--400


Theoretical Computer Science
Volume 3, Number 1, October, 1976

               L. J. Stockmeyer   The polynomial-time hierarchy  . . . . . 1--22
                    C. Wrathall   Complete sets and the polynomial-time
                                  hierarchy  . . . . . . . . . . . . . . . 23--33
                   G. Lallement   Regular semigroups with D=R as syntactic
                                  monoids of prefix codes  . . . . . . . . 35--49
                        G. Hotz   Conditions for balanced trees on
                                  weighted distributions . . . . . . . . . 51--59
                      B. Monien   A recursive and a grammatical
                                  characterization of the exponential-time
                                  languages  . . . . . . . . . . . . . . . 61--74
                   K. Culik, II   On the decidability of the sequence
                                  equivalence problem for D0L-systems  . . 75--84
                   T. Araki and   
                      T. Kasami   Some decision problems related to the
                                  reachability problem for Petri nets  . . 85--104
                N. D. Jones and   
                   W. T. Laaser   Complete problems for deterministic
                                  polynomial time  . . . . . . . . . . . . 105--117

Theoretical Computer Science
Volume 3, Number 2, November, 1976

               D. C. Jensen and   
               T. Pietrzykowski   Mechanizing omega-order type theory
                                  through unification  . . . . . . . . . . 123--171
                        D. Park   Finiteness is mu-ineffable . . . . . . . 173--181
                 W. Lipski, Jr.   Information storage and
                                  retrieval-mathematical foundations II.
                                  Combinatorial problems . . . . . . . . . 183--211
               J. Hartmanis and   
                      L. Berman   On tape bounds for single letter
                                  alphabet language processing . . . . . . 213--224
                  H. Barendregt   A global representation of the recursive
                                  functions in the lambda -calculus  . . . 225--242
           M. P. Schutzenberger   On the rational relations between free
                                  monoids  . . . . . . . . . . . . . . . . 243--259
                   P. H. Starke   Analysis and synthesis of asynchronous
                                  ND-automata  . . . . . . . . . . . . . . 261--266
                   A. Schonhage   An elementary proof for Strassen's
                                  degree bound . . . . . . . . . . . . . . 267--272

Theoretical Computer Science
Volume 3, Number 3, December, 1976

                T. G. Szymanski   Concerning bounded-right-context
                                  grammars . . . . . . . . . . . . . . . . 273--282
                    K. Ruohonen   Zeros of Z-rational functions and D0L
                                  equivalence  . . . . . . . . . . . . . . 283--292
              A. K. Chandra and   
           D. S. Hirschberg and   
                     C. K. Wong   Approximate algorithms for some
                                  generalized knapsack problems  . . . . . 293--304
                       C. Beeri   An improvement on Valiant's decision
                                  procedure for equivalence of
                                  deterministic finite turn pushdown
                                  machines . . . . . . . . . . . . . . . . 305--320
                D. E. Knuth and   
                    L. T. Pardo   Analysis of a simple factorization
                                  algorithm  . . . . . . . . . . . . . . . 321--348
               R. J. Lipton and   
                      D. Dobkin   Complexity measures and hierarchies for
                                  the evaluation of integers and
                                  polynomials  . . . . . . . . . . . . . . 349--357
                     D. S. Wise   A strong pumping lemma for context-free
                                  languages  . . . . . . . . . . . . . . . 359--369
               R. L. Rivest and   
                   J. Vuillemin   On recognizing graph properties from
                                  adjacency matrices . . . . . . . . . . . 371--384


Theoretical Computer Science
Volume 4, Number 1, February, 1977

                      R. Milner   Fully abstract models of typed lambda
                                  -calculi . . . . . . . . . . . . . . . . 1--22
                       Z. Galil   On the complexity of regular resolution
                                  and the Davis--Putnam procedure  . . . . 23--46
           H. P. Schutzenberger   On a variant of sequential functions . . 47--57
                  D. J. Lehmann   Algebraic structures for transitive
                                  closure  . . . . . . . . . . . . . . . . 59--76
                   J. Vuillemin   How to verify the connectivity of a
                                  group table  . . . . . . . . . . . . . . 77--82
                       M. Linna   A decidability result for deterministic
                                  omega-context-free languages . . . . . . 83--98
                   T. Araki and   
                      T. Kasami   Decidable problems on the strong
                                  connectivity of Petri net reachability
                                  sets . . . . . . . . . . . . . . . . . . 99--119

Theoretical Computer Science
Volume 4, Number 2, April, 1977

                   G. Markowsky   Categories of chain-complete posets  . . 125--135
                  C. Hosono and   
                        M. Sato   The retracts in P omega do not form a
                                  continuous lattice --- a solution to
                                  Scott's problem  . . . . . . . . . . . . 137--142
               M. M. Geller and   
            H. B. Hunt, III and   
            T. G. Szymanski and   
                   J. D. Ullman   Economy of description by parsers,
                                  DPDA's, and PDA's  . . . . . . . . . . . 143--153
                     J. Francon   On the analysis of algorithms for trees  155--169
                    H.-G. Stork   On the paging-complexity of periodic
                                  arrangements . . . . . . . . . . . . . . 171--197
                  H. Maurer and   
                Th. Ottmann and   
                     A. Salomaa   On the form equivalence of L-forms . . . 199--225
                J. Ferrante and   
                   J. R. Geiser   An efficient decision procedure for the
                                  theory of rational order . . . . . . . . 227--233
                  D. J. Lehmann   A note on Schnorr's separatedness  . . . 235

Theoretical Computer Science
Volume 4, Number 3, June, 1977

            C. H. Papadimitriou   The Euclidean traveling salesman problem
                                  is NP-complete . . . . . . . . . . . . . 237--244
               M. M. Geller and   
                 M. A. Harrison   On LR(k) grammars and languages  . . . . 245--276
                N. D. Jones and   
            L. H. Landweber and   
                     Y. E. Lien   Complexity of some problems in Petri
                                  nets . . . . . . . . . . . . . . . . . . 277--299
                       R. Daley   On the inference of optimal descriptions 301--319
               T. Olshansky and   
                      A. Pnueli   A direct algorithm for checking
                                  equivalence of LL(k) grammars  . . . . . 321--349


Theoretical Computer Science
Volume 5, Number 1, August, 1977

                 W. A. Burkhard   Non-uniform partial-match file designs   1--23
                    Y. S. Kwong   On reduction of asynchronous systems . . 25--50
                     L. Chottin   Syntactical study of certain language
                                  solutions of operator equations  . . . . 51--84
                  J. Engelfriet   Iterating iterated substitution  . . . . 85--100

Theoretical Computer Science
Volume 5, Number 2, October, 1977

                  A. Mandel and   
                       I. Simon   On finite semigroups of matrices . . . . 101--111
              A. B. Cremers and   
                  T. N. Hibbard   On the formal definition of dependencies
                                  between the control and information
                                  structure of a data space  . . . . . . . 113--128
                     M. Latteux   Product in the rational cone produced by
                                  D/sub 1/*  . . . . . . . . . . . . . . . 129--134
                  L. Aiello and   
                  M. Aiello and   
                R. W. Weyhrauch   PASCAL in LCF: semantics and examples of
                                  proof  . . . . . . . . . . . . . . . . . 135--177
                   Z. Galil and   
                     N. Megiddo   Cyclic ordering is NP-complete . . . . . 179--182
                       G. Jacob   An algorithm for calculating the
                                  cardinal, finite or infinite, of the
                                  semigroups of matrices . . . . . . . . . 183--204
                 M. D. Atkinson   The complexity of group algebra
                                  computations . . . . . . . . . . . . . . 205--209
                   J. Karhumaki   Remarks on commutative $N$-rational
                                  series . . . . . . . . . . . . . . . . . 211--217
                  C. Reutenauer   On a question of S. Eilenberg (rational
                                  sequences) . . . . . . . . . . . . . . . 219

Theoretical Computer Science
Volume 5, Number 3, December, 1977

                  G. D. Plotkin   LCF considered as a programming language 223--255
                    M. B. Smyth   Effectively given domains  . . . . . . . 257--274
                C. C. Elgot and   
                      L. Snyder   On the many facets of lists  . . . . . . 275--305
                S. Ginsburg and   
                  E. H. Spanier   Pushdown acceptor forms  . . . . . . . . 307--320
                   H. Luckhardt   A fundamental effect in computations on
                                  real numbers . . . . . . . . . . . . . . 321--324
                    C. Choffrut   Rational relations characterization of
                                  sequential and subsequential functions   325--337
               G. Rozenberg and   
               M. Penttonen and   
                     A. Salomaa   Bibliography of L systems  . . . . . . . 339--354


Theoretical Computer Science
Volume 6, Number 1, February, 1978

                R. S. Cohen and   
                     A. Y. Gold   Omega-computations on Turing machines    1--23
                       N. Lynch   Log space machines with multiple oracle
                                  tapes  . . . . . . . . . . . . . . . . . 25--39
                     H. Abelson   Towards a theory of local and global in
                                  computation  . . . . . . . . . . . . . . 41--67
               K. Culik, II and   
               H. A. Maurer and   
                    Th. Ottmann   On two-symbol complete E0L Forms . . . . 69--92
              D. S. Johnson and   
                F. P. Preparata   The densest hemisphere problem . . . . . 93--107

Theoretical Computer Science
Volume 6, Number 2, April, 1978

                   Z. Manna and   
                      A. Shamir   The convergence of functions to fixed
                                  points of recursive definitions  . . . . 109--141
               K. Culik, II and   
               H. A. Maurer and   
                Th. Ottmann and   
                K. Ruohonen and   
                     A. Salomaa   Isomorphism, form equivalence and
                                  sequence equivalence of DP0L forms . . . 143--173
                 S. A. Greibach   One way finite visit automata  . . . . . 175--221
                     C. Rackoff   The covering and boundedness problems
                                  for vector addition systems  . . . . . . 223--231

Theoretical Computer Science
Volume 6, Number 3, June, 1978

             V. L. Bennison and   
                    R. I. Soare   Some lowness properties and
                                  computational complexity sequences . . . 233--254
                   B. Courcelle   A representation of trees by languages.
                                  I  . . . . . . . . . . . . . . . . . . . 255--279
                D. E. Knuth and   
                   A. Schonhage   The expected linearity of a simple
                                  equivalence algorithm  . . . . . . . . . 281--315
                 D. Bollman and   
                     M. Laplaza   Some decision problems for polynomial
                                  mappings . . . . . . . . . . . . . . . . 317--325
             A. Ehrenfeucht and   
                   G. Rozenberg   E0L languages are not codings or FP0L
                                  languages  . . . . . . . . . . . . . . . 327--341


Theoretical Computer Science
Volume 7, Number 1, August, 1978

                H. F. de Groote   On varieties of optimal algorithms for
                                  the computation of bilinear mappings. I.
                                  The isotropy group of a bilinear mapping 1--24
                   B. Courcelle   A representation of trees by languages.
                                  II . . . . . . . . . . . . . . . . . . . 25--55
               J. B. Wright and   
               E. G. Wagner and   
                 J. W. Thatcher   A uniform approach to inductive posets
                                  and inductive closure  . . . . . . . . . 57--77
               P. van Emde Boas   Some applications of the McCreight-Meyer
                                  algorithm in abstract complexity theory  79--98
                 R. Verbeek and   
                   K. Weihrauch   Data representation and computational
                                  complexity . . . . . . . . . . . . . . . 99--116
                    M. Mignotte   Intersection of images of certain
                                  recurrent linear series  . . . . . . . . 117--121

Theoretical Computer Science
Volume 7, Number 2, October, 1978

                H. F. de Groote   On varieties of optimal algorithms for
                                  the computation of bilinear mappings.
                                  II. Optimal algorithms for 2*2-matrix
                                  multiplication . . . . . . . . . . . . . 127--148
                   K. Kobayashi   On the minimal firing time of the firing
                                  squad synchronization problem for
                                  polyautomata networks  . . . . . . . . . 149--167
             A. Ehrenfeucht and   
                   G. Rozenberg   Elementary homomorphisms and a solution
                                  of the D0L sequence equivalence problem  169--183
                 R. V. Book and   
                    C. Wrathall   On languages specified by relative
                                  acceptance . . . . . . . . . . . . . . . 185--195
                   J.-F. Perrot   Varieties of languages and operations    197--210
                      J. E. Pin   On the syntactic monoid of L* where L is
                                  a finite language  . . . . . . . . . . . 211--215
               D. E. Muller and   
                F. P. Preparata   Finding the intersection of two convex
                                  polyhedra  . . . . . . . . . . . . . . . 217--236

Theoretical Computer Science
Volume 7, Number 3, December, 1978

                H. F. de Groote   On varieties of optimal algorithms for
                                  the computation of bilinear mappings.
                                  III. Optimal algorithms for the
                                  computation of $xy$ and $yx$ where $x,y$
                                  in $M_2(K)$  . . . . . . . . . . . . . . 239--249
                  C. P. Schnorr   Improved lower bounds on the number of
                                  multiplications/divisions which are
                                  necessary to evaluate polynomials  . . . 251--261
                       S. Skyum   On good ET0L forms . . . . . . . . . . . 263--272
                   J. Hartmanis   On log-tape isomorphisms of complete
                                  sets . . . . . . . . . . . . . . . . . . 273--286
                   O. H. Ibarra   On two-way sequential transductions of
                                  full semi-AFLs . . . . . . . . . . . . . 287--309
                 S. A. Greibach   Remarks on blind and partially blind
                                  one-way multicounter machines  . . . . . 311--324
                 M. Kleiman and   
                   N. Pippenger   An explicit construction of short
                                  monotone formulae for the monotone
                                  symmetric functions  . . . . . . . . . . 325--332
                 E. P. Friedman   A note on non-singular deterministic
                                  pushdown automata  . . . . . . . . . . . 333--339


Theoretical Computer Science
Volume 8, Number 1, February, 1979

           E. Soisalon-Soininen   On the covering problem for
                                  left-recursive grammars  . . . . . . . . 1--11
                        M. Wand   Fixed-point constructions in
                                  order-enriched categories  . . . . . . . 13--30
                       W. Bibel   Tautology testing with a generalised
                                  matrix reduction method  . . . . . . . . 31--44
            F. P. Preparata and   
                   D. E. Muller   Finding the intersection of n
                                  half-spaces in time O(n log n) . . . . . 45--55
                    P. Johansen   The generating function of the number of
                                  subpatterns of a D0L sequence  . . . . . 57--68
                  K. Hashiguchi   A decision procedure for the order of
                                  regular events . . . . . . . . . . . . . 69--72
                  K. R. Apt and   
             J. A. Bergstra and   
           L. G. L. T. Meertens   Recursive assertions are not enough-or
                                  are they?  . . . . . . . . . . . . . . . 73--87
                  M. E. Majster   Data types, abstract data types and
                                  their specification problem  . . . . . . 89--127

Theoretical Computer Science
Volume 8, Number 2, April, 1979

                J. Hopcroft and   
                  J.-J. Pansiot   On the reachability problem for
                                  $5$-dimensional vector addition systems  135--159
               H. Prodinger and   
                  F. J. Urbanek   Language operators related to Init . . . 161--175
                T. P. Baker and   
                   A. L. Selman   A second step toward the polynomial
                                  hierarchy  . . . . . . . . . . . . . . . 177--187
                  L. G. Valiant   The complexity of computing the
                                  permanent  . . . . . . . . . . . . . . . 189--201
                  P. Pudlak and   
              F. N. Springsteel   Complexity in mechanized hypothesis
                                  formation  . . . . . . . . . . . . . . . 203--225
                       P. Hajek   Arithmetical hierarchy and complexity of
                                  computation  . . . . . . . . . . . . . . 227--237
                   J. Hartmanis   Relations between diagonalization, proof
                                  systems, and complexity gaps . . . . . . 239--253
                 J. Morgenstern   An extension of Winograd's theorem . . . 255--259
                  A. Arnold and   
                     M. Latteux   A new proof of two theorems about
                                  rational transductions . . . . . . . . . 261--263

Theoretical Computer Science
Volume 8, Number 3, June, 1979

                    C. Bohm and   
      M. Dezani-Ciancaglini and   
                 P. Peretti and   
                 S. R. D. Rocca   A discrimination algorithm inside
                                  $\lambda$-$\beta$-calculus . . . . . . . 271--291
                   J. Beauquier   Algebraic generation and systems of
                                  iterative pairs  . . . . . . . . . . . . 293--323
                C. C. Elgot and   
              J. C. Shepherdson   A semantically meaningful
                                  characterization of reducible flowchart
                                  schemes  . . . . . . . . . . . . . . . . 325--357
                    S. Winograd   On multiplication in algebraic extension
                                  fields . . . . . . . . . . . . . . . . . 359--377
                       D. Dolev   Commutation properties and generating
                                  sets characterize slices of various
                                  synchronization primitives . . . . . . . 379--391
                     R. Hindley   The discrimination theorem holds for
                                  combinatory weak reduction . . . . . . . 393--394
                 J.-M. Autebert   A note on the cylinder of deterministic
                                  languages  . . . . . . . . . . . . . . . 395--399


Theoretical Computer Science
Volume 9, Number 1, July, 1979

                 D. A. Plaisted   Fast verification, testing, and
                                  generation of large primes . . . . . . . 1--16
                    J.-P. Duval   Relationship between global periodicity
                                  and repetitions of words . . . . . . . . 17--26
                J. Bergstra and   
                     J. W. Klop   Church--Rosser strategies in the lambda
                                  calculus . . . . . . . . . . . . . . . . 27--38
                  I. Guessarian   Program transformations and algebraic
                                  semantics  . . . . . . . . . . . . . . . 39--65
                     R. Statman   Intuitionistic propositional logic is
                                  polynomial-space complete  . . . . . . . 67--72
                     R. Statman   The typed lambda -calculus is not
                                  elementary recursive . . . . . . . . . . 73--81
                     I. Wegener   Switching functions whose monotone
                                  complexity is nearly quadratic . . . . . 83--97
                P. Flajolet and   
               J. C. Raoult and   
                   J. Vuillemin   The number of registers required for
                                  evaluating arithmetic expressions  . . . 99--125
                G. Wechsung and   
                  A. Brandstadt   A relation between space, return and
                                  dual return complexities . . . . . . . . 127--140
                    G. Christol   Almost $k$-recognisable periodic sets    141--145
                     I. Wegener   A counterexample to a conjecture of
                                  Schnorr referring to monotone networks   147--150

Theoretical Computer Science
Volume 9, Number 2, August, 1979

                        A. Tang   Chain properties in P omega  . . . . . . 153--172
             M. A. Harrison and   
                I. M. Havel and   
                     A. Yehudai   On equivalence of grammars through
                                  transformation trees . . . . . . . . . . 173--205
                   J. Karhumaki   On commutative DT0L systems  . . . . . . 207--220
                      D. Perrin   The ergodic representation of finite
                                  automata . . . . . . . . . . . . . . . . 221--241
             E. A. Ashcroft and   
                     F. E. Fich   A generalized setting for fixpoint
                                  theory . . . . . . . . . . . . . . . . . 243--256
                S. L. Bloom and   
                     R. Tendell   Algebraic and graph theoretic
                                  characterizations of structured
                                  flowchart schemes  . . . . . . . . . . . 265--286
                     A. Nijholt   Simple chain grammars and languages  . . 287--309
                   K. Inoue and   
                I. Takanami and   
                A. Nakamura and   
                          T. Ae   One-way simple multihead finite automata 311--328
                       R. Aubin   Mechanizing structural induction. I.
                                  Formal system  . . . . . . . . . . . . . 329--346
                       R. Aubin   Mechanizing structural induction. II.
                                  Strategies . . . . . . . . . . . . . . . 347--362
                  C. Reutenauer   On the associated series to certain
                                  Lindenmayer systems  . . . . . . . . . . 363--375
                    K. Ruohonen   On some decidability problems for HD0L
                                  systems with nonsingular Parikh matrices 377--384
                   F. Rodriguez   Families of closed languages by open
                                  brackets . . . . . . . . . . . . . . . . 385--398