Table of contents for issues of Theoretical Computer Science

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

Volume 35, Number 1, January, 1985
Volume 35, Number 2--3, February, 1985
Volume 36, Number 1, March, 1985
Volume 36, Number 2--3, April, 1985
Volume 37, Number 1, May, 1985
Volume 37, Number 2, November, 1985
Volume 37, Number 3, December, 1985
Volume 38, Number 1, May, 1985
Volume 38, Number 2--3, June, 1985
Volume 39, Number 1, July, 1985
Volume 39, Number 2--3, August, 1985
Volume 40, Number 1, September, 1985
Volume 40, Number 2--3, 1985
Volume 41, Number 1, 1985
Volume 41, Number 2--3, 1985
Volume 42, Number 1, May, 1986
Volume 42, Number 2, August, 1986
Volume 42, Number 3, October, 1986
Volume 43, Number 1, May, 1986
Volume 43, Number 2--3, 1986
Volume 44, Number 1, 1986
Volume 44, Number 2, 1986
Volume 44, Number 3, 1986
Volume 45, Number 1, 1986
Volume 45, Number 2, 1986
Volume 45, Number 3, 1986
Volume 46, Number 1, 1986
Volume 46, Number 2--3, 1986
Volume 47, Number 1, 1986
Volume 47, Number 2, 1986
Volume 47, Number 3, 1986
Volume 48, Number 1, 1986
Volume 48, Number 2--3, 1986
Volume 49, Number 1, 1987
Volume 49, Number 2--3, 1987
Volume 50, Number 1, 1987
Volume 50, Number 2, 1987
Volume 50, Number 3, 1987
Volume 51, Number 1--2, 1987
Volume 51, Number 3, 1987
Volume 52, Number 1--2, 1987
Volume 52, Number 3, 1987
Volume 53, Number 1, 1987
Volume 53, Number 2--3, 1987
Volume 54, Number 1, September, 1987
Volume 54, Number 2--3, October, 1987
Volume 55, Number 1, November, 1987
Volume 55, Number 2--3, December, 1987
Volume 56, Number 1, January, 1988
Volume 56, Number 2, February, 1988
Volume 56, Number 3, March, 1988
Volume 57, Number 1, April, 1988
Volume 57, Number 2--3, May, 1988
Volume 58, Number 1-3, June, 1988
Volume 59, Number 1--2, July, 1988
Volume 59, Number 3, August, 1988
Volume 60, Number 1, March, 1988
Volume 60, Number 2, September, 1988
Volume 60, Number 3, December, 1988
Volume 61, Number 1, October, 1988
Volume 61, Number 2--3, November, 1988
Volume 62, Number 1--2, December, 1988
Volume 62, Number 3, December, 1988
Volume 63, Number 1, January, 1989
Volume 63, Number 2, February, 1989
Volume 63, Number 3, March, 1989
Volume 64, Number 1, April, 1989
Volume 64, Number 2, May 7, 1989
Volume 64, Number 3, May 29, 1989
Volume 65, Number 1, June 15, 1989
Volume 65, Number 2, June 28, 1989
Volume 65, Number 3, July 17, 1989
Volume 66, Number 1, August 2, 1989
Volume 66, Number 2, August 20, 1989
Volume 66, Number 3, August 26, 1989
Volume 67, Number 1, September 5, 1989
Volume 67, Number 2--3, October 3, 1989
Volume 68, Number 1, October 16, 1989
Volume 68, Number 2, October 30, 1989
Volume 68, Number 3, November 12, 1989
Volume 69, Number 1, December 5, 1989
Volume 69, Number 2, December 11, 1989
Volume 69, Number 3, December 18, 1989
Volume 302, Number 1--3, June 13, 2003


Theoretical Computer Science
Volume 35, Number 1, January, 1985

                K.-J. Lange and   
                       E. Welzl   Recurrent words and simultaneous growth
                                  in T0L systems . . . . . . . . . . . . . 1--15
                       J. Stern   Characterizations of some classes of
                                  regular events . . . . . . . . . . . . . 17--42
                S. L. Bloom and   
                  D. R. Troeger   A logical characterization of
                                  observation equivalence  . . . . . . . . 43--53
                H. Edelsbrunner   Finding transversals for sets of simple
                                  geometric figures  . . . . . . . . . . . 55--69
                    Y. Metivier   Calculation of the length of rewriting
                                  chains in free monoide . . . . . . . . . 71--87
                      C. Benoit   Axiomatisation of tests  . . . . . . . . 89--107
                   D. Kapur and   
       M. S. Krishnamoorthy and   
              R. McNaughton and   
                  Narendran and   
                             P.   An $O(\bmod {T} \bmod ^3)$ algorithm for
                                  testing the Church--Rosser property of
                                  Thue systems . . . . . . . . . . . . . . 109--114
                 J.-P. Pecuchet   Two-way finite automata and finite words 115--122

Theoretical Computer Science
Volume 35, Number 2--3, February, 1985

                    L. Fribourg   A superposition oriented theorem prover  129--164
                G. Ausiello and   
                  A. d'Atri and   
                   M. Moscarini   On the existence of acyclic views in a
                                  database scheme  . . . . . . . . . . . . 165--177
                    R. Cori and   
                    Y. Metivier   Recognizable subsets of some partially
                                  Abelian monoids  . . . . . . . . . . . . 179--189
                   G. Memmi and   
                      A. Finkel   An introduction to FIFO nets-monogeneous
                                  nets: a subclass of FIFO nets  . . . . . 191--214
                   K. Kobayashi   On proving time constructibility of
                                  functions  . . . . . . . . . . . . . . . 215--225
               P. Narendran and   
                        F. Otto   Complexity results on the conjugacy
                                  problem for monoids  . . . . . . . . . . 227--243
                 D. A. Plaisted   Complete divisibility problems for
                                  slowly utilized oracles  . . . . . . . . 245--260
                  S. Hirose and   
                   S. Okawa and   
                      M. Yoneda   A homomorphic characterization of
                                  recursively enumerable languages . . . . 261--269
                  J.-E. Pin and   
                 J. Sakarovitch   An application of the matrix
                                  representation of transductions  . . . . 271--293
                    T. Head and   
                   J. Wilkinson   Code properties and homomorphisms of D0L
                                  systems  . . . . . . . . . . . . . . . . 295--312
                       E. Leiss   On classes of tractable unrestricted
                                  regular expressions  . . . . . . . . . . 313--327
                  M. Oyamaguchi   On the data type extension problem for
                                  algebraic specifications . . . . . . . . 329--336
                   D. Kapur and   
                   P. Narendran   A finite Thue system with decidable word
                                  problem and without equivalent finite
                                  canonical system . . . . . . . . . . . . 337--344
                        I. Sain   A simple proof for the completeness of
                                  Floyd's method . . . . . . . . . . . . . 345--348


Theoretical Computer Science
Volume 36, Number 1, March, 1985

                        M. Broy   On the Herbrand-Kleene universe for
                                  nondeterministic computations  . . . . . 1--19
                  J. Engelfriet   Determinacy to (observation
                                  equivalence=trace equivalence) . . . . . 21--25
                     R. Janicki   Transforming sequential systems into
                                  concurrent systems . . . . . . . . . . . 27--58
                        N. Blum   An $\Omega(n^4/3)$ lower bound on the
                                  monotone network complexity of the
                                  $n^{th}$ degree convolution  . . . . . . 59--69
              M. L. Tiomkin and   
                 J. A. Makowsky   Propositional dynamic logic with local
                                  assignments  . . . . . . . . . . . . . . 71--87
                    Y. Igarashi   A pumping lemma for real-time
                                  deterministic context-free languages . . 89--97
                   C. De Felice   Construction of factorisation codes  . . 99--108
                  S. Hirose and   
                      M. Yoneda   On the Chomsky and Stanley's homomorphic
                                  characterization of context-free
                                  languages  . . . . . . . . . . . . . . . 109--112
                    K. Ruohonen   On equality of multiplicity sets of
                                  regular languages  . . . . . . . . . . . 113--117
                 B. Scarpellini   Complex Boolean networks obtained by
                                  diagonalization  . . . . . . . . . . . . 119--125
                     G. Winskel   On powerdomains and modality . . . . . . 127--137

Theoretical Computer Science
Volume 36, Number 2--3, April, 1985

               N. E. Fenton and   
               R. W. Whitty and   
                   A. A. Kaposi   A generalised mathematical theory of
                                  structured programming . . . . . . . . . 145--171
           I. H. Sudborough and   
                       E. Welzl   Complexity and decidability for chain
                                  code picture languages . . . . . . . . . 173--202
                   J. Demel and   
                 M. Demlova and   
                      V. Koubek   Fast algorithms constructing minimal
                                  subalgebras, congruences, and ideals in
                                  a finite algebra . . . . . . . . . . . . 203--216
                    M. Kaminski   A classification of omega-regular
                                  languages  . . . . . . . . . . . . . . . 217--229
                E. Allender and   
                    M. M. Klawe   Improved lower bounds for the cycle
                                  detection problem  . . . . . . . . . . . 231--237
                   R. Fagin and   
                M. M. Klawe and   
            N. J. Pippenger and   
                  L. Stockmeyer   Bounded-depth, polynomial-size circuits
                                  for symmetric functions  . . . . . . . . 239--250
       L. Farinas Del Cerro and   
                    E. Orlowska   DAL-a logic for data analysis  . . . . . 251--264
                   M. R. Jerrum   The complexity of finding minimum-length
                                  generator sequences  . . . . . . . . . . 265--289
                 H. Matsuno and   
                   K. Inoue and   
               H. Taniguchi and   
                    I. Takanami   Alternating simple multihead finite
                                  automata . . . . . . . . . . . . . . . . 291--308
               W. Keller-Gehrig   Fast algorithms for the characteristic
                                  polynomial . . . . . . . . . . . . . . . 309--317
                        K. Diks   Embeddings of binary trees in lines  . . 319--331
                         H. Alt   Multiplication is the easiest nontrivial
                                  arithmetic function  . . . . . . . . . . 333--339
                  W. Rytter and   
                     M. Chrobak   A characterization of reversal-bounded
                                  multipushdown machine languages  . . . . 341--344
                    G. Farr and   
                   C. McDiarmid   The complexity of counting homeomorphs   345--348


Theoretical Computer Science
Volume 37, Number 1, May, 1985

                          K. Ko   On some natural complete operators . . . 1--30
                   G. Rozenberg   On coordinated selective substitutions:
                                  towards a unified theory of grammars and
                                  machines . . . . . . . . . . . . . . . . 31--50
               D. E. Muller and   
                   P. E. Schupp   The theory of ends, pushdown automata,
                                  and second-order logic . . . . . . . . . 51--75
             J. A. Bergstra and   
                     J. W. Klop   Algebra of communicating processes with
                                  abstraction  . . . . . . . . . . . . . . 77--121

Theoretical Computer Science
Volume 37, Number 2, November, 1985

              J. H. Gallier and   
                     R. V. Book   Reductions in tree replacement systems   123--150
                       L. Bouge   A contribution to the theory of program
                                  testing  . . . . . . . . . . . . . . . . 151--181
               K. Culik, II and   
                        I. Fris   Topological transformations as a tool in
                                  the design of systolic networks  . . . . 183--216
            J. Gonczarowski and   
                  M. K. Warmuth   Applications of scheduling theory to
                                  formal language theory . . . . . . . . . 217--243

Theoretical Computer Science
Volume 37, Number 3, December, 1985

                   R. de Simone   Higher-level synchronising devices in
                                  MEIJE-SCCS . . . . . . . . . . . . . . . 245--267
                    A. Tarlecki   On the existence of free models in
                                  abstract algebraic institutions  . . . . 269--304
                   P. Darondeau   About fair asynchrony  . . . . . . . . . 305--336
             A. Ehrenfeucht and   
            H. C. M. Kleijn and   
                   G. Rozenberg   Adding global forbidding context to
                                  context-free grammars  . . . . . . . . . 357--360


Theoretical Computer Science
Volume 38, Number 1, May, 1985

                  M. P. Fle and   
                   G. Roucairol   Maximal serializability of iterated
                                  transactions . . . . . . . . . . . . . . 1--16
                   K. Weihrauch   Type 2 recursion theory  . . . . . . . . 17--33
                  C. Kreitz and   
                   K. Weihrauch   Theory of representations  . . . . . . . 35--53
                     I. Wegener   On the complexity of slice functions . . 55--68
                        M. Snir   Lower bounds on probabilistic linear
                                  decision trees . . . . . . . . . . . . . 69--82
              P. V. Ramanan and   
                      C. L. Liu   Permutation representation of $k$-ary
                                  trees  . . . . . . . . . . . . . . . . . 83--98
                   C. Beeri and   
                    M. Y. Vardi   Formal systems for join dependencies . . 99--116
                     M. Leconte   A characterization of power-free
                                  morphisms  . . . . . . . . . . . . . . . 117--122
                      D. L. Van   Code-compatible sets and a
                                  generalisation of the Sardinas-Patterson
                                  theorem  . . . . . . . . . . . . . . . . 123--132
                       E. Leiss   Succinct representation of regular
                                  languages by Boolean automata. II  . . . 133--136
                      A. Finkel   A generalisation of the theorems of
                                  Higman and of Simon to infinite words    137--142

Theoretical Computer Science
Volume 38, Number 2--3, June, 1985

                     D. Schmidt   The recursion-theoretic structure of
                                  complexity classes . . . . . . . . . . . 143--156
                    O. Watanabe   On one-one polynomial time equivalence
                                  relations  . . . . . . . . . . . . . . . 157--165
                   M. Imori and   
                      H. Yamada   Periodic character sequences where
                                  identifying two characters strictly
                                  reduces the period . . . . . . . . . . . 167--192
                 H. D. Burkhard   An investigation of controls for
                                  concurrent systems based on abstract
                                  control languages  . . . . . . . . . . . 193--122
                     M. Jantzen   Extending regular expressions with
                                  iterated shuffle . . . . . . . . . . . . 223--247
                       T. Asano   An approach to the subgraph
                                  homeomorphism problem  . . . . . . . . . 249--267
                  B. Mishra and   
                      E. Clarke   Hierarchical verification of
                                  asynchronous circuits using temporal
                                  logic  . . . . . . . . . . . . . . . . . 269--291
                 T. F. Gonzalez   Clustering to minimize the maximum
                                  intercluster distance  . . . . . . . . . 293--306
                   D. Harel and   
                       D. Peleg   Process logic with regular formulas  . . 307--322
          D. J. Rosenkrantz and   
                H. B. Hunt, III   Testing for grammatical coverings  . . . 323--341
                  N. Linial and   
                       M. Tarsi   Deciding hypergraph $2$-colourability by
                                  H-resolution . . . . . . . . . . . . . . 343--347


Theoretical Computer Science
Volume 39, Number 1, July, 1985

                      Anonymous   Third Conference on Foundations of
                                  Software Technology and Theoretical
                                  Computer Science . . . . . . . . . . . . ??
                     C. Frougny   Context-free grammars with cancellation
                                  properties . . . . . . . . . . . . . . . 3--13
               J.-L. Lassez and   
                    M. J. Maher   Optimal fixedpoints of logic programs    15--25
                    C. Stirling   A proof-theoretic characterization of
                                  observational equivalence  . . . . . . . 27--45
              R. J. R. Back and   
                     H. Mannila   On the suitability of trace semantics
                                  for modular proofs of communicating
                                  processes  . . . . . . . . . . . . . . . 47--68
                      R. Kannan   Solving systems of linear equations over
                                  polynomials  . . . . . . . . . . . . . . 69--88

Theoretical Computer Science
Volume 39, Number 2--3, August, 1985

               O. H. Ibarra and   
                M. A. Palis and   
                    J. H. Chang   On efficient recognition of
                                  transductions and relations  . . . . . . 89--106
                      L. Priese   On a fast decomposition method in some
                                  models of concurrent computations  . . . 107--121
                   D. Kapur and   
               P. Narendran and   
       M. S. Krishnamoorthy and   
                 McNaughton and   
                             R.   The Church--Rosser property and special
                                  Thue systems . . . . . . . . . . . . . . 123--133
                    C. Bohm and   
                  A. Berarducci   Automatic synthesis of typed Lambda
                                  -programs on term algebras . . . . . . . 135--153
                 M. Parigot and   
                        E. Pelz   A logical approach of Petri net
                                  languages  . . . . . . . . . . . . . . . 155--169
                  J.-C. Spehner   Entire systems of equations on a finite
                                  alphabet and Ehrenfeucht's conjecture    171--188
          M. Rodriguez Artalejo   Some questions about expressiveness and
                                  relative completeness in Hoare's logic   189--206
              S. R. Mahaney and   
                       P. Young   Reductions among polynomial isomorphism
                                  types  . . . . . . . . . . . . . . . . . 207--224
                  D. Joseph and   
                       P. Young   Some remarks on witness functions for
                                  nonpolynomial and noncomplete sets in NP 225--237
                        R. Hull   Non-finite specifiability of projections
                                  of functional dependency families  . . . 239--265
                   J. Vogel and   
                      K. Wagner   Two-way automata with more than one
                                  storage medium . . . . . . . . . . . . . 267--280
               R. Siromoney and   
                     V. R. Dare   On infinite words obtained by selective
                                  substitution grammars  . . . . . . . . . 281--295
                       A. Haken   The intractability of resolution . . . . 297--308
                S. Ginsburg and   
                  E. H. Spanier   On completing tables to satisfy
                                  functional dependencies  . . . . . . . . 309--317
                 R. V. Book and   
                        F. Otto   On the security of name-stamp protocols  319--325
                    E. L. Leiss   On solving star equations  . . . . . . . 327--332
                      A. Arnold   A syntactic congruence for rational
                                  omega-languages  . . . . . . . . . . . . 333--335
                   M. W. Bunder   An extension of Klop's counterexample to
                                  the Church--Rosser property to
                                  lambda-calculus with other ordered pair
                                  combinators  . . . . . . . . . . . . . . 337--342


Theoretical Computer Science
Volume 40, Number 1, September, 1985

                   J. Karhumaki   On three-element codes . . . . . . . . . 3--11
                 A. Restivo and   
                  C. Reutenauer   Rational languages and the Burnside
                                  problem  . . . . . . . . . . . . . . . . 13--30
                  A. Blumer and   
                  J. Blumer and   
                D. Haussler and   
             A. Ehrenfeucht and   
                       Chen and   
                      M. T. and   
                    J. Seiferas   The smallest automation recognizing the
                                  subwords of a text . . . . . . . . . . . 31--55
                    U. Schoning   Robust algorithms: a different approach
                                  to oracles . . . . . . . . . . . . . . . 57--66
                   R. Paige and   
               R. E. Tarjan and   
                       R. Bonic   A linear time solution to the single
                                  function coarsest partition problem  . . 67--84

Theoretical Computer Science
Volume 40, Number 2--3, 1985

                       G. Bauer   n-level rewriting systems  . . . . . . . 85--99
                 R. V. Book and   
                        F. Otto   On the verifiability of two-party
                                  algebraic protocols  . . . . . . . . . . 101--130
                  W. Bucher and   
             A. Ehrenfeucht and   
                    D. Haussler   On total regulators generated by
                                  derivation relations . . . . . . . . . . 131--148
       I. J. J. Aalbersberg and   
                   G. Rozenberg   CTS systems and Petri nets . . . . . . . 149--162
                       K. Ayers   Deque automata and a subfamily of
                                  context-sensitive languages which
                                  contains all semilinear bounded
                                  languages  . . . . . . . . . . . . . . . 163--174
                   K. Kobayashi   On the structure of one-tape
                                  nondeterministic Turing machine time
                                  hierarchy  . . . . . . . . . . . . . . . 175--193
          Ming-Deh A. Huang and   
               K. J. Lieberherr   Implications of forbidden structures for
                                  extremal algorithmic problems  . . . . . 195--210
                 G. Mascari and   
             M. Venturini Zilli   While-programs with nondeterministic
                                  assignments and the logic ALNA . . . . . 211--235
             J. L. Balcazar and   
                 R. V. Book and   
                    U. Schoning   On bounded query machines  . . . . . . . 237--243
                 T. Kanaoka and   
                      S. Tomita   Homogeneous decomposition of stochastic
                                  systems  . . . . . . . . . . . . . . . . 245--255
               S. K. Abdali and   
                 B. D. Saunders   Transitive closure and related semiring
                                  properties via eliminants  . . . . . . . 257--274
             F. Fogelman-Soulie   Parallel and sequential computation on
                                  Boolean networks . . . . . . . . . . . . 275--300
                A. Ginzburg and   
                       M. Yoeli   Reducibility of synchronization
                                  structures . . . . . . . . . . . . . . . 301--314
                  F. J. Urbanek   On Greibach normal form construction . . 315--317
                    M. Kaminski   A lower bound for polynomial
                                  multiplication . . . . . . . . . . . . . 319--322
       M. S. Krishnamoorthy and   
                   P. Narendran   On recursive path ordering . . . . . . . 323--328
                    G. Gonthier   Algebraic calculi of processes and net
                                  expressions  . . . . . . . . . . . . . . 329--337


Theoretical Computer Science
Volume 41, Number 1, 1985

                      G. P\uaun   A variant of random context grammars:
                                  semi-conditional grammars  . . . . . . . 1--17
                       E. Goles   Dynamics of positive automata networks   19--32
                V. E. Cazanescu   On context-free trees  . . . . . . . . . 33--50
                       P. Gohon   An algorithm to decide whether a
                                  rational subset of $N^k$ is recognizable 51--59
          E. Barbin-Le Rest and   
                     M. Le Rest   On the combinatorial of two-word codes   61--80
               C. S. Iliopoulos   Computing in general Abelian groups is
                                  hard . . . . . . . . . . . . . . . . . . 81--93
                     S. Hayashi   Adjunction of semifunctors: categorical
                                  structures in nonextensional Lambda
                                  calculus . . . . . . . . . . . . . . . . 95--104
                        Y. Maon   On the equivalence problem of
                                  compositions of morphisms and inverse
                                  morphisms on context-free languages  . . 105--107
                   J.-Y. Thibon   Integrity of algebras of formal series
                                  on a partially commutative alphabet  . . 109--112
                   M. W. Bunder   Possible forms of evaluation or
                                  reduction in Martin-Löf type theory . . . 113--120
               M. H. Albert and   
                    J. Lawrence   A proof of Ehrenfeucht's conjecture  . . 121--123

Theoretical Computer Science
Volume 41, Number 2--3, 1985

                    B. Helfrich   Algorithms to construct Minkowski
                                  reduced and Hermite reduced lattice
                                  bases  . . . . . . . . . . . . . . . . . 125--139
                  B. Monien and   
               I. H. Sudborough   Bandwidth constrained NP-complete
                                  problems . . . . . . . . . . . . . . . . 141--167
                E. Dahlhaus and   
                     H. Gaifman   Concerning two-adjacent context-free
                                  languages  . . . . . . . . . . . . . . . 169--184
                      W. Reisig   Petri nets with individual tokens  . . . 185--213
                   J. Karhumaki   A property of three-element codes  . . . 215--222
                  E. Tomita and   
                       K. Seino   A weaker sufficient condition for the
                                  equivalence of a pair of DPDAs to be
                                  decidable  . . . . . . . . . . . . . . . 223--230
               O. H. Ibarra and   
                M. A. Palis and   
                      S. M. Kim   Fast parallel language recognition by
                                  cellular automata  . . . . . . . . . . . 231--246
                        E. Pelz   On the complexity of theories of
                                  permutations . . . . . . . . . . . . . . 247--269
                   J. Grant and   
                      J. Minker   Inferences for numerical dependencies    271--287
                    S. Hirokawa   Complexity of the combinator reduction
                                  machine  . . . . . . . . . . . . . . . . 289--303
                     G. Slutzki   Alternating tree automata  . . . . . . . 305--318
                    H.-J. Stoss   The complexity of evaluating
                                  interpolation polynomials  . . . . . . . 319--323
         F. Meyer Auf Der Heide   Simulating probabilistic by
                                  deterministic algebraic computation
                                  trees  . . . . . . . . . . . . . . . . . 325--330
                   K. Inoue and   
                I. Takanami and   
                     R. Vollmar   Alternating on-line Turing machines with
                                  only universal states and small space
                                  bounds . . . . . . . . . . . . . . . . . 331--339


Theoretical Computer Science
Volume 42, Number 1, May, 1986

                   B. Courcelle   Equivalences and transformations of
                                  regular systems-applications to
                                  recursive program schemes and grammars   1--122

Theoretical Computer Science
Volume 42, Number 2, August, 1986

                     M. Wirsing   Structured algebraic specifications: a
                                  kernel language  . . . . . . . . . . . . 123--249

Theoretical Computer Science
Volume 42, Number 3, October, 1986

              J. Engelfriet and   
                      H. Vogler   Pushdown machines for the macro tree
                                  transducer . . . . . . . . . . . . . . . 251--368


Theoretical Computer Science
Volume 43, Number 1, May, 1986

       J. W. Grzymala-Busse and   
                       Z. Bavel   Characterization of state-independent
                                  automata . . . . . . . . . . . . . . . . 1--10
                    A. Scheuing   Decomposition of linear automata over
                                  residue rings into shift-registers . . . 11--30
                       C. Ronse   A topological characterization of
                                  thinning . . . . . . . . . . . . . . . . 31--41
         L. M. Goldschlager and   
                    I. Parberry   On the construction of parallel
                                  computers from various bases of Boolean
                                  functions  . . . . . . . . . . . . . . . 43--58
             R. R. Redziejowski   Infinite-word languages and continuous
                                  mappings . . . . . . . . . . . . . . . . 59--79
                    E. Orlowska   Semantic analysis of inductive reasoning 81--89
                      G. Hansel   The demonstration of a simple proof of
                                  Skolem-Mahler-Lech theorem . . . . . . . 91--98
                       P. Clote   On the finite containment problem for
                                  Petri nets . . . . . . . . . . . . . . . 99--105
                  P. A. Lindsay   Alternation and omega-type Turing
                                  acceptors  . . . . . . . . . . . . . . . 107--115
               M. H. Albert and   
                    J. Lawrence   Test sets for finite substitutions . . . 117--122

Theoretical Computer Science
Volume 43, Number 2--3, 1986

              R. Berghammer and   
                      H. Zierer   Relational algebraic semantics of
                                  deterministic and nondeterministic
                                  programs . . . . . . . . . . . . . . . . 123--147
                     J. Heering   Partial evaluation and
                                  omega-completeness of algebraic
                                  specifications . . . . . . . . . . . . . 149--167
               M. R. Jerrum and   
              L. G. Valiant and   
                 V. V. Vazirani   Random generation of combinatorial
                                  structures from a uniform distribution   169--188
                   F. Fages and   
                        G. Huet   Complete sets of unifiers and matchers
                                  in equational theories . . . . . . . . . 189--200
                     I. Wegener   More on the complexity of slice
                                  functions  . . . . . . . . . . . . . . . 201--211
                 R. Janicki and   
                P. E. Lauer and   
                  M. Koutny and   
                   R. Devillers   Concurrent and maximally concurrent
                                  evolution of nonsequential systems . . . 213--238
               G. M. Landau and   
                     U. Vishkin   Efficient string matching with k
                                  mismatches . . . . . . . . . . . . . . . 239--249
                 A. Pasztor and   
                     R. Statman   Scott induction and closure under
                                  omega-sups . . . . . . . . . . . . . . . 251--263
                 A. de Luca and   
                     A. Restivo   Star-free sets of integers . . . . . . . 265--275
                  I. Suzuki and   
               Y. Motohashi and   
               K. Taniguchi and   
                  T. Kasami and   
                     T. Okamoto   Specification and verification of
                                  decentralized daisy chain arbiters with
                                  omega-extended regular expressions . . . 277--291
                  J. Adamek and   
               J. Reiterman and   
                      E. Nelson   Continuous semilattices  . . . . . . . . 293--313
                      A. Saoudi   Varieties of automata deriving from
                                  infinite trees . . . . . . . . . . . . . 315--335
                     K. Edwards   The complexity of colouring problems on
                                  dense graphs . . . . . . . . . . . . . . 337--343
                  D. B. Johnson   A simple proof of a time-space trade-off
                                  for sorting with linear comparisons  . . 345--350


Theoretical Computer Science
Volume 44, Number 1, 1986

                    P. Ritzmann   A fast numerical algorithm for the
                                  composition of power series with complex
                                  coefficients . . . . . . . . . . . . . . 1--16
               F. Blanchard and   
                      G. Hansel   Coded systems  . . . . . . . . . . . . . 17--49
                     D. Leivant   Typing and computational properties of
                                  lambda expressions . . . . . . . . . . . 51--68
               L. E. Rosier and   
                      H.-C. Yen   Boundedness, empty channel detection,
                                  and synchronization for communicating
                                  finite automata  . . . . . . . . . . . . 69--105
               F. Blanchard and   
                    S. Martinez   Dense orbit points of certain languages
                                  of infinite words  . . . . . . . . . . . 107--110
                J. H. Chang and   
               O. H. Ibarra and   
                M. A. Palis and   
                   B. Ravikumar   On pebble automata . . . . . . . . . . . 111--121

Theoretical Computer Science
Volume 44, Number 2, 1986

                        E. Paul   On solving the equality problem in
                                  theories defined by Horn clauses . . . . 127--153
                    E. L. Leiss   Generalized language equations with
                                  multiple solutions . . . . . . . . . . . 155--174
                   Y. Kobayashi   Repetition-free words  . . . . . . . . . 175--197
                     V. Diekert   Complete semi-Thue systems for Abelian
                                  groups . . . . . . . . . . . . . . . . . 199--208
                      T. Etzion   An algorithm for generating
                                  shift-register cycles  . . . . . . . . . 209--224
                   S. Okawa and   
                  S. Hirose and   
                      M. Yoneda   On the impossibility of the homomorphic
                                  characterization of context-sensitive
                                  languages  . . . . . . . . . . . . . . . 225--228
                  F. J. Urbanek   On Greibach normal form construction . . 229--236
                   P. Narendran   On the equivalence problem for regular
                                  Thue systems . . . . . . . . . . . . . . 237--245

Theoretical Computer Science
Volume 44, Number 3, 1986

                    P. E. Dunne   The complexity of central slice
                                  functions  . . . . . . . . . . . . . . . 247--257
                   M. Takahashi   The greatest fixed-points and rational
                                  omega-tree languages . . . . . . . . . . 259--274
             H.-J. Kreowski and   
                     A. Wilharm   Net processes correspond to derivation
                                  processes in graph grammars  . . . . . . 275--305
              W. F. Dowling and   
                  J. H. Gallier   Continuation semantics for flowgraph
                                  equations  . . . . . . . . . . . . . . . 307--331
                  E. T. Poulsen   The Ehrenfeucht Conjecture: an
                                  algebra-framework for its proof  . . . . 333--339


Theoretical Computer Science
Volume 45, Number 1, 1986

                        M. Broy   A theory for nondeterminism,
                                  parallelism, communication, and
                                  concurrency  . . . . . . . . . . . . . . 1--61
                  M. Crochemore   Transducers and repetitions  . . . . . . 63--86
                J. Gonczarowski   Manipulating derivation forests by
                                  scheduling techniques  . . . . . . . . . 87--119

Theoretical Computer Science
Volume 45, Number 2, 1986

      M. Dezani-Ciancaglini and   
                    I. Margaria   A characterization of F-complete type
                                  assignments  . . . . . . . . . . . . . . 121--157
                   J.-Y. Girard   The system F of variable types, fifteen
                                  years later  . . . . . . . . . . . . . . 159--192
                J.-J. Ch. Meyer   Merging regular processes by means of
                                  fixed-point theory . . . . . . . . . . . 193--260

Theoretical Computer Science
Volume 45, Number 3, 1986

                   P. Huber and   
               A. M. Jensen and   
               L. O. Jepsen and   
                      K. Jensen   Reachability trees for high-level Petri
                                  nets . . . . . . . . . . . . . . . . . . 261--292
                    H. Ait-Kaci   An algebraic semantics approach to the
                                  effective resolution of type equations   293--351


Theoretical Computer Science
Volume 46, Number 1, 1986

                  G. Bernot and   
                  M. Bidoit and   
                      C. Choppy   Abstract data types with exception
                                  handling: an initial approach based on a
                                  distinction between exceptions and
                                  errors . . . . . . . . . . . . . . . . . 13--45
                  Y. Q. Guo and   
                   G. W. Xu and   
                    G. Thierrin   Disjunctive decomposition of languages   47--51
                  K. Hashiguchi   Notes on finitely generated semigroups
                                  and pumping conditions for regular
                                  languages  . . . . . . . . . . . . . . . 53--66
                   N. Lerat and   
                 W. Lipski, Jr.   Nonapplicable nulls  . . . . . . . . . . 67--82
                    T. Head and   
                       B. Lando   Periodic D0L languages . . . . . . . . . 83--89
                H. Yamasaki and   
               M. Takahashi and   
                   K. Kobayashi   Characterization of omega-regular
                                  languages by monadic second-order
                                  formulas . . . . . . . . . . . . . . . . 91--99
                 M. Latteux and   
                   E. Timmerman   Two characterizations of rational
                                  adherences . . . . . . . . . . . . . . . 101--106

Theoretical Computer Science
Volume 46, Number 2--3, 1986

               R. R. Howell and   
               L. E. Rosier and   
              Dung T. Huynh and   
                   Hsu-Chun Yen   Some complexity bounds for problems
                                  concerning finite and $2$- dimensional
                                  vector addition systems with states  . . 107--140
                  J. Jaffar and   
                  P. J. Stuckey   Semantics of infinite tree logic
                                  programming  . . . . . . . . . . . . . . 141--158
                       C. Duboc   On some equations in free partially
                                  commutative monoids  . . . . . . . . . . 159--174
                  A. Brazma and   
                      E. Kinber   Generalized regular expressions-a
                                  language for synthesis of programs with
                                  branching in loops . . . . . . . . . . . 175--195
                   G. Longo and   
                     S. Martini   Computability in higher types, P omega
                                  and the completeness of type assignment  197--217
             Phan Dinh Dieu and   
              Le Cong Thanh and   
                    Le Tuan Hoa   Average polynomial time complexity of
                                  some NP-complete problems  . . . . . . . 219--237
                       P. Hajek   A simple dynamic logic . . . . . . . . . 239--259
           Chua-Huang Huang and   
                    C. Lengauer   The automated proof of a trace
                                  transformation for a bitonic sort  . . . 261--284
                       A. Dicky   An algebraic and algorithmic method for
                                  analysing transition systems . . . . . . 285--303
                  T. Hardin and   
                     A. Laville   Proof of termination of the rewriting
                                  system SUBST on CCL  . . . . . . . . . . 305--312
                     V. Diekert   On some variants of the Ehrenfeucht
                                  Conjecture . . . . . . . . . . . . . . . 313--318
                     V. Diekert   Commutative monoids have complete
                                  presentations by free (non-commutative)
                                  monoids  . . . . . . . . . . . . . . . . 319--327
                    B. Griesser   Lower bounds for the approximative
                                  complexity . . . . . . . . . . . . . . . 329--338


Theoretical Computer Science
Volume 47, Number 1, 1986

                    Z. Esik and   
                      P. Domosi   Complete classes of automata for the
                                  $\alpha_0$-product . . . . . . . . . . . 1--14
               K. Culik, II and   
                       Sheng Yu   Real-time, pseudo real-time, and
                                  linear-time ITA  . . . . . . . . . . . . 15--26
               P. Narendran and   
                        F. Otto   The problems of cyclic equality and
                                  conjugacy for finite complete rewriting
                                  systems  . . . . . . . . . . . . . . . . 27--38
                  J. H. Johnson   Rational equivalence relations . . . . . 39--60
                        A. Pelc   Lie patterns in search procedures  . . . 61--69
               K. Culik, II and   
                   J. Karhumaki   The equivalence of finite valued
                                  transducers (on HDT0L languages) is
                                  decidable  . . . . . . . . . . . . . . . 71--84
              L. G. Valiant and   
                 V. V. Vazirani   NP is as easy as detecting unique
                                  solutions  . . . . . . . . . . . . . . . 85--93
                 J.-P. Pecuchet   On the complementation of Buchi Automata 95--98
                      J. Heintz   On polynomials with symmetric Galois
                                  group which are easy to compute  . . . . 99--105
                    P. Wyrostek   On the size of unambiguous context-free
                                  grammars . . . . . . . . . . . . . . . . 107--110

Theoretical Computer Science
Volume 47, Number 2, 1986

                   P. W. Dymond   On nondeterminism in parallel
                                  computation  . . . . . . . . . . . . . . 111--120
                     P. Orponen   A classification of complexity core
                                  lattices . . . . . . . . . . . . . . . . 121--130
                   K. W. Wagner   Some observations on the connection
                                  between counting and recursion . . . . . 131--147
                     M. Chrobak   Finite automata and unary languages  . . 149--158
                 V. R. Dare and   
                   R. Siromoney   Subword topology . . . . . . . . . . . . 159--168
                       S. Homer   On simple and creative sets in NP  . . . 169--180
                  J.-C. Spehner   The rapid calculation of shuffles of two
                                  words  . . . . . . . . . . . . . . . . . 191--203
             L. M. Kirousis and   
            C. H. Papadimitriou   Searching and pebbling . . . . . . . . . 205--218
               R. Parchmann and   
                       J. Duske   Self-embedding indexed grammars  . . . . 219--223
                        F. Otto   The undecidability of self-embedding for
                                  finite semi-Thue and Thue systems  . . . 225--232

Theoretical Computer Science
Volume 47, Number 3, 1986

                    M. Karchmer   Two time-space tradeoffs for element
                                  distinctness . . . . . . . . . . . . . . 237--246
                    Y. Maon and   
                     A. Yehudai   Balance of many-valued transductions and
                                  equivalence problems . . . . . . . . . . 247--262
                   Ker-I Ko and   
                 T. J. Long and   
                       D.-Z. Du   On one-way functions and polynomial-time
                                  isomorphisms . . . . . . . . . . . . . . 263--276
                    Y. Maon and   
                B. Schieber and   
                     U. Vishkin   Parallel ear decomposition search (EDS)
                                  and st-numbering in graphs . . . . . . . 277--298
                       Ker-I Ko   On the continued fraction representation
                                  of computable real numbers . . . . . . . 299--313
                      W. Rytter   On the complexity of parallel parsing of
                                  general context-free languages . . . . . 315--321
                 J. W. Hong and   
                         Q. Zuo   Lower bounds on communication overlap of
                                  networks . . . . . . . . . . . . . . . . 323--328
                      Z. Szalas   Concerning the semantic consequence
                                  relation in first-order temporal logic   329--334
              J.-L. Deleage and   
                      L. Pierre   The rational index of the Dyck language
                                  $D_1'*$  . . . . . . . . . . . . . . . . 335--343


Theoretical Computer Science
Volume 48, Number 1, 1986

                    Z. Esik and   
                      F. Gecseg   On $\alpha_0$-products and
                                  $\alpha_2$-products  . . . . . . . . . . 1--8
                       K.-I. Ko   On the notion of infinite pseudorandom
                                  sequences  . . . . . . . . . . . . . . . 9--33
                  J.-C. Spehner   The occurrence of the factors of a given
                                  word in a text . . . . . . . . . . . . . 35--52
                 S. Bublitz and   
               U. Schurfeld and   
                 I. Wegener and   
                       B. Voigt   Properties of complexity measures for
                                  PRAMs and WRAMs  . . . . . . . . . . . . 53--73
              C. P. Kruskal and   
                        M. Snir   A unified theory of interconnection
                                  network structure  . . . . . . . . . . . 75--94
                     R. Statman   Every countable poset is embeddable in
                                  the poset of unsolvable terms  . . . . . 95--100
                    T. Head and   
                       B. Lando   Regularity of sets of initial strings of
                                  periodic D0L-systems . . . . . . . . . . 101--108
                   J. Hromkovic   Communication complexity hierarchy . . . 109--115
                   G. Berry and   
                       R. Sethi   From regular expressions to
                                  deterministic automata . . . . . . . . . 117--126
                V. Weispfenning   The complexity of the word problem for
                                  Abelian $l$-groups . . . . . . . . . . . 127--132

Theoretical Computer Science
Volume 48, Number 2--3, 1986

                    M. Tchuente   Sequential simulation of parallel
                                  iterations and applications  . . . . . . 135--144
                   W. Marek and   
                     H. Rasiowa   Approximating sets with equivalence
                                  relations  . . . . . . . . . . . . . . . 145--152
                     M. Chrobak   Hierarchies of one-way multihead
                                  automata languages . . . . . . . . . . . 153--181
                       C. Duboc   Mixed product and asynchronous automata  183--199
             A. Ehrenfeucht and   
            H. J. Hoogeboom and   
                   G. Rozenberg   On the active and full use of memory in
                                  right-boundary grammars and push-down
                                  automata . . . . . . . . . . . . . . . . 201--228
                     M. Fitting   Partial models and logic programming . . 229--255
                       W. Danko   First-order approximation of algorithmic
                                  theories . . . . . . . . . . . . . . . . 257--272
                 G. F. Italiano   Amortized efficiency of a path retrieval
                                  data structure . . . . . . . . . . . . . 273--281
                 A. Salomaa and   
                          S. Yu   On a public-key cryptosystem based on
                                  iterated morphisms and substitutions . . 283--296
                S. Ginsburg and   
                        C. Tang   Projection of object histories . . . . . 297--328
                 A. Gibbons and   
                      W. Rytter   On the decidability of some problems
                                  about rational subsets of free partially
                                  commutative monoids  . . . . . . . . . . 329--337


Theoretical Computer Science
Volume 49, Number 1, 1987

                   M. Takahashi   Brzozowski hierarchy of omega-languages  1--12
                   C. C. Squier   Units of special Church--Rosser monoids  13--22
               R. Parchmann and   
                       J. Duske   Grammars, derivation modes and
                                  properties of indexed and type-0
                                  languages  . . . . . . . . . . . . . . . 23--42
                  M. Oyamaguchi   The Church--Rosser property for ground
                                  term-rewriting systems is decidable  . . 43--79
               L. J. Guibas and   
                  J. Stolfi and   
                 K. L. Clarkson   Solving related two- and
                                  three-dimensional linear programming
                                  problems in logarithmic time . . . . . . 81--84

Theoretical Computer Science
Volume 49, Number 2--3, 1987

                      Anonymous   Twelfth International Colloquium on
                                  Automata, Languages and Programming  . . ??
            J. W. de Bakker and   
             J.-J. C. Meyer and   
                  E.-R. Olderog   Infinite streams and finite observations
                                  in the semantics of uniform concurrency  87--112
                 M. G. Main and   
                  W. Bucher and   
                    D. Haussler   Applications of an infinite square-free
                                  co-CFL . . . . . . . . . . . . . . . . . 113--119
                    M. Hennessy   An algebraic theory of fair asynchronous
                                  communicating processes  . . . . . . . . 121--143
                       L. Bouge   Repeated snapshots in distributed
                                  systems with synchronous communications
                                  and their implementation in CSP  . . . . 145--169
                   Z. Galil and   
               G. M. Landau and   
                     M. M. Yung   Distributed algorithms in synchronous
                                  broadcasting networks  . . . . . . . . . 171--184
                   K. G. Larsen   A context dependent equivalence between
                                  processes  . . . . . . . . . . . . . . . 185--215
           A. Prasad Sistla and   
                M. Y. Vardi and   
                      P. Wolper   The complementation problem for Buchi
                                  automata with applications to temporal
                                  logic  . . . . . . . . . . . . . . . . . 217--237
                        R. Cole   Partitioning point sets in arbitrary
                                  dimension  . . . . . . . . . . . . . . . 239--265
                T. G. Kurtz and   
                      U. Manber   A probabilistic distributed algorithm
                                  for set intersection and its analysis    267--282
                    P. Flajolet   Analytic models and ambiguity of
                                  context-free languages . . . . . . . . . 283--309
                    C. Stirling   Modal logics for communicating systems   311--347


Theoretical Computer Science
Volume 50, Number 1, 1987

                   J.-Y. Girard   Linear logic . . . . . . . . . . . . . . 1--102

Theoretical Computer Science
Volume 50, Number 2, 1987

                     J. W. Gray   Categorical aspects of data type
                                  constructors . . . . . . . . . . . . . . 103--135
             J. A. Bergstra and   
                   J. V. Tucker   Algebraic specifications of computable
                                  and semicomputable data types  . . . . . 137--181
                     J. Mazoyer   A six-state minimal time solution to the
                                  firing squad synchronization problem . . 183--238

Theoretical Computer Science
Volume 50, Number 3, 1987

                    I. Phillips   Refusal testing  . . . . . . . . . . . . 241--284
                        I. Sain   Total correctness in nonstandard logics
                                  of programs  . . . . . . . . . . . . . . 285--321
               E. G. Wagner and   
                       H. Ehrig   Canonical constraints for parameterized
                                  data types . . . . . . . . . . . . . . . 323--349


Theoretical Computer Science
Volume 51, Number 1--2, 1987

                A. S. Troelstra   On the syntax of Martin-Löf's type
                                  theories . . . . . . . . . . . . . . . . 1--26
                 P. Le Chenadec   Analysis of Dehn's algorithm by critical
                                  pairs  . . . . . . . . . . . . . . . . . 27--52
                   K. W. Wagner   More complicated questions about maxima
                                  and minima, and some closures of NP  . . 53--80
                   A. Habel and   
                 H. J. Kreowski   Characteristics of graph languages
                                  generated by edge replacement  . . . . . 81--115
               J. Beauquier and   
                        F. Gire   A note on the characterisation theorem
                                  for algebraic generators . . . . . . . . 117--127
            J. C. M. Baeten and   
             J. A. Bergstra and   
                     J. W. Klop   On the consistency of Koomen's fair
                                  abstraction rule . . . . . . . . . . . . 129--176
             K. Ambos-Spies and   
             H. Fleischhack and   
                       H. Huwig   Diagonalizations over polynomial time
                                  computable sets  . . . . . . . . . . . . 177--204
                      F. Orejas   A characterization of passing
                                  compatibility for parameterized
                                  specifications . . . . . . . . . . . . . 205--214
                       A. Carpi   On unambiguous reductions of monoids of
                                  unambiguous relations  . . . . . . . . . 215--220
                      J. Vyskoc   An $O(n^{lgk}.2^n2)$ time and
                                  $O(k.2^nk)$ space algorithm for certain
                                  NP-complete problems . . . . . . . . . . 221--227
                   E. G. Belaga   Constructive universal algebra: an
                                  introduction . . . . . . . . . . . . . . 229--238
                    I. Parberry   On the time required to sum n semigroup
                                  elements on a parallel machine with
                                  simultaneous writes  . . . . . . . . . . 239--247

Theoretical Computer Science
Volume 51, Number 3, 1987

                    T. Head and   
                       B. Lando   Bounded DL languages . . . . . . . . . . 255--264
                   S. Homer and   
                     T. J. Long   Honest polynomial degrees and P=?NP  . . 265--280
               B. Bérard   Literal shuffle (formal languages) . . . 281--299
                    T. Yokomori   On purely morphic characterizations of
                                  context-free languages . . . . . . . . . 301--308
                S. Yamasaki and   
                 M. Yoshida and   
                     S. Doshita   A fixpoint semantics of Horn sentences
                                  based on substitution sets . . . . . . . 309--324
                   J. Hromkovic   Reversal-bounded nondeterministic
                                  multicounter machines and
                                  complementation  . . . . . . . . . . . . 325--330
                        T. Beth   On the computational complexity of the
                                  general discrete Fourier transform . . . 331--339
                   Z. Galil and   
                   R. Giancarlo   Parallel string matching with k
                                  mismatches . . . . . . . . . . . . . . . 341--348


Theoretical Computer Science
Volume 52, Number 1--2, 1987

                      M. Zaionc   Word operation definable in the typed
                                  lambda-calculus  . . . . . . . . . . . . 1--14
                       K. I. Ko   On helping by robust oracle machines . . 15--36
                    R. Kennaway   On 'On graph rewritings' . . . . . . . . 37--58
                 J. Sakarovitch   On regular trace languages . . . . . . . 59--75
              J. von zur Gathen   Factoring polynomials and primitive
                                  elements for special primes  . . . . . . 77--89
                       B. Seite   A Yacc extension for LRR grammar parsing 91--143
                     D. Mundici   Satisfiability in many-valued sentential
                                  logic is NP-complete . . . . . . . . . . 145--153
                    P. Spirakis   The parallel complexity of deadlock
                                  detection  . . . . . . . . . . . . . . . 155--163
                      T. Moriya   Topological characterizations of
                                  infinite tree languages  . . . . . . . . 165--171

Theoretical Computer Science
Volume 52, Number 3, 1987

                     C. Kim and   
               I. H. Sudborough   The membership and equivalence problems
                                  for picture languages  . . . . . . . . . 177--191
              J. M. Marberg and   
                       E. Gafni   Distributed sorting algorithms for
                                  multi-channel broadcast networks . . . . 193--203
               M. Felleisen and   
             D. P. Friedman and   
              E. Kohlbecker and   
                        B. Duba   A syntactic theory of sequential control 205--237
              R. G. Nigmatullin   Models of lower-bounds proofs  . . . . . 239--249
             J. L. Balcazar and   
                    J. Diaz and   
                     J. Gabarro   On characterizations of the class
                                  PSPACE\slash poly  . . . . . . . . . . . 251--267
                 E. Gelenbe and   
                      D. Finkel   Stationary deterministic flows. II. The
                                  single-server queue  . . . . . . . . . . 269--280
                    R. W. Topor   Domain-independent formulas and
                                  databases  . . . . . . . . . . . . . . . 281--306
                  G. Stefanescu   On flowchart theories. II. The
                                  nondeterministic case  . . . . . . . . . 307--340
              F. J. Brandenburg   Comments on 'Deque automata and a
                                  subfamily of context-sensitive languages
                                  which contains all semilinear bounded
                                  languages' . . . . . . . . . . . . . . . 341--342


Theoretical Computer Science
Volume 53, Number 1, 1987

                      Anonymous   Eleventh Colloquium on Trees in Algebra
                                  and Programming  . . . . . . . . . . . . ??
                   E. G. Wagner   A categorical treatment of pre- and
                                  post-conditions  . . . . . . . . . . . . 3--24
                        G. File   Classical and incremental attribute
                                  evaluation by means of recursive
                                  procedures . . . . . . . . . . . . . . . 25--65
               D. Frutos Escrig   Probabilistic Ianov's schemes  . . . . . 67--97
                    G. Louchard   Random walks, Gaussian processes and
                                  list structures  . . . . . . . . . . . . 99--124
                   A. Pelin and   
                  J. H. Gallier   Building exact computation sequences . . 125--150
                  A. Pettorossi   Derivation of efficient programs for
                                  computing sequences of actions . . . . . 151--167

Theoretical Computer Science
Volume 53, Number 2--3, 1987

                  H. Attiya and   
                     Y. Mansour   Language complexity on the synchronous
                                  anonymous ring . . . . . . . . . . . . . 169--185
                I. Litovsky and   
                   E. Timmerman   On generators of rational omega-power
                                  languages  . . . . . . . . . . . . . . . 187--200
                  C. P. Schnorr   A hierarchy of polynomial time lattice
                                  basis reduction algorithms . . . . . . . 201--224
                    S. Abramsky   Observation equivalence as a testing
                                  equivalence  . . . . . . . . . . . . . . 225--241
                    Z. Esik and   
                      F. Gecseg   On a representation of tree automata . . 243--255
                  H. Muller and   
                  A. Brandstadt   The NP-completeness of Steiner tree and
                                  dominating set for chordal bipartite
                                  graphs . . . . . . . . . . . . . . . . . 257--265
                  M. Beynon and   
                      J. Buckle   On the planar monotone computation of
                                  Boolean functions  . . . . . . . . . . . 267--279
                   D. Peleg and   
                       E. Upfal   The generalized packet routing problem   281--293
                  W. Rytter and   
                   R. Giancarlo   Optimal parallel parsing of bracket
                                  languages  . . . . . . . . . . . . . . . 295--306
                      M. Garzon   Cyclic automata  . . . . . . . . . . . . 307--317
                 T. Nishida and   
                     Y. Kobuchi   Repeatable words for substitution  . . . 319--333
                     L. Hallnas   An intensional characterization of the
                                  largest bisimulation . . . . . . . . . . 335--343
                 N. Santoro and   
               J. B. Sidney and   
               S. J. Sidney and   
                     J. Urrutia   Geometric containment and vector
                                  dominance  . . . . . . . . . . . . . . . 345--352


Theoretical Computer Science
Volume 54, Number 1, September, 1987

                Jieh Hsiang and   
                      M. Srivas   Automatic inductive theorem proving
                                  using PROLOG . . . . . . . . . . . . . . 3--28
               F. V. Jensen and   
                   K. D. Larsen   Recursively defined domains and their
                                  induction principles . . . . . . . . . . 29--51
        A. Marchetti-Spaccamela   New protocols for the election of a
                                  leader in a ring . . . . . . . . . . . . 53--64
                         V. Pan   Complexity of parallel matrix
                                  computations . . . . . . . . . . . . . . 65--85
                       C. Bajaj   Geometric optimization and the
                                  polynomial hierarchy . . . . . . . . . . 87--102
           V. S. Lakshmanan and   
            C. E. Veni Madhavan   An algebraic theory of functional and
                                  multivalued dependencies in relational
                                  databases  . . . . . . . . . . . . . . . 103--128
               S. M. Venkatesan   Approximation algorithms for weighted
                                  matching . . . . . . . . . . . . . . . . 129--137

Theoretical Computer Science
Volume 54, Number 2--3, October, 1987

                  L. Priese and   
                R. Rehrmann and   
             U. Willecke-Klemme   An introduction to the regular theory of
                                  fairness . . . . . . . . . . . . . . . . 139--163
                     G. Rindone   Construction of a family of codes
                                  associated with certain finite groups    165--179
              A. Brandstadt and   
                     D. Kratsch   On domination problems for permutation
                                  and other graphs . . . . . . . . . . . . 181--198
                      A. Szalas   A complete axiomatic characterization of
                                  first-order temporal logic of linear
                                  time . . . . . . . . . . . . . . . . . . 199--214
               J. R. B. Cockett   Discrete decision theory: manipulations  215--236
              P. Bertolazzi and   
                     A. Sassano   An O(mn) algorithm for regular
                                  set-covering problems  . . . . . . . . . 237--247
                    O. Watanabe   A comparison of polynomial time
                                  completeness notions . . . . . . . . . . 249--265
               D. E. Muller and   
                   P. E. Schupp   Alternating automata on infinite trees   267--276
                  H. Fauconnier   Asynchronous semantics and infinite
                                  behaviour in CSP . . . . . . . . . . . . 277--298
                S. Ginsburg and   
                 Chang-jie Tang   Canonical forms for interval functions   299--313
                    K. Sado and   
                    Y. Igarashi   A function for evaluating the computing
                                  time of a bubbling system  . . . . . . . 315--324
                   S. Iwata and   
                       T. Kasai   Simultaneous (poly-time, log-space)
                                  lower bounds . . . . . . . . . . . . . . 325--329
              M. Liskiewicz and   
                   K. Lorys and   
                     M. Piotrow   On reversal bounded alternating Turing
                                  machines . . . . . . . . . . . . . . . . 331--339
                       K.-I. Ko   On the continued fraction representation
                                  of computable real numbers . . . . . . . 341--343


Theoretical Computer Science
Volume 55, Number 1, November, 1987

                       D. Peleg   Concurrent program schemes and their
                                  logics . . . . . . . . . . . . . . . . . 1--45
                       H. Seidl   Parameter-reduction of higher level
                                  grammars . . . . . . . . . . . . . . . . 47--85
                    E. Best and   
                   R. Devillers   Sequential and concurrent behaviour in
                                  Petri net theory . . . . . . . . . . . . 87--136

Theoretical Computer Science
Volume 55, Number 2--3, December, 1987

                   B. Courcelle   An axiomatic definition of context-free
                                  rewriting and its application to NLC
                                  graph grammars . . . . . . . . . . . . . 141--181
              F.-J. Brandenburg   Representations of language families by
                                  homomorphic equality operations and
                                  generalized equality sets  . . . . . . . 183--263
                      M. Bartha   An equational axiomatization of systolic
                                  systems  . . . . . . . . . . . . . . . . 265--289
                  J.-P. Lehmann   A universal machine without change of
                                  state  . . . . . . . . . . . . . . . . . 291--348


Theoretical Computer Science
Volume 56, Number 1, January, 1988

                  D. Armbruster   A polynomial determination of the
                                  most-recent property in Pascal-like
                                  programs . . . . . . . . . . . . . . . . 3--15
                  C. Hankin and   
                    G. Burn and   
                S. Peyton Jones   A safe approach to parallel combinator
                                  reduction  . . . . . . . . . . . . . . . 17--36
                      S. Kaplan   Rewriting with a nondeterministic choice
                                  operator . . . . . . . . . . . . . . . . 37--57
                 F. Nielson and   
                  H. R. Nielson   Two-level semantics and code generation  59--133
                    E. W. Stark   Proving entailment between conceptual
                                  state specifications . . . . . . . . . . 135--154

Theoretical Computer Science
Volume 56, Number 2, February, 1988

                 E. Fachini and   
                      M. Napoli   C-tree systolic automata . . . . . . . . 155--186
                       W. Marek   A natural semantics for modal logic over
                                  databases  . . . . . . . . . . . . . . . 187--209
               C. S. Iliopoulos   On the computational complexity of the
                                  Abelian permutation group structure,
                                  membership and intersection problems . . 211--222
                S. Sekimoto and   
                    S. Hirokawa   One-step recurrent terms in
                                  $\lambda$-$\beta$-calculus . . . . . . . 223--231
                       A. Carpi   Multidimensional unrepetitive
                                  configurations . . . . . . . . . . . . . 233--241
                    J. Mohrherr   A remark on the length problem . . . . . 243--248

Theoretical Computer Science
Volume 56, Number 3, March, 1988

                    C. Tretkoff   Complexity, combinatorial group theory
                                  and the language of palutators . . . . . 253--275
                     J. Staples   Delaying unification algorithms for
                                  lambda calculi . . . . . . . . . . . . . 277--288
                      E. Gradel   Subclasses of Presburger arithmetic and
                                  the polynomial-time hierarchy  . . . . . 289--301
                     A. Martino   A quantitative interpretation of
                                  Girard's system $F$  . . . . . . . . . . 303--320
            R. Boonyavatana and   
                     G. Slutzki   The interchange or pump (DI)lemmas for
                                  context-free languages . . . . . . . . . 321--338
                     V. Bruyere   An answer to a question about finite
                                  maximal prefix sets of words . . . . . . 339--344
                  F. Baader and   
                     W. Buttner   Unification in commutative idempotent
                                  monoids  . . . . . . . . . . . . . . . . 345--353


Theoretical Computer Science
Volume 57, Number 1, April, 1988

                        M. Broy   Equational specification of partial
                                  higher-order algebras  . . . . . . . . . 3--45
               O. H. Ibarra and   
                    M. A. Palis   Two-dimensional iterative arrays:
                                  characterizations and applications . . . 47--86
                    F. M. Ablyv   The complexity properties of
                                  probabilistic automata with isolated cut
                                  point  . . . . . . . . . . . . . . . . . 87--95
                   J. Hromkovic   The advantages of a new approach to
                                  defining the communication complexity
                                  for VLSI . . . . . . . . . . . . . . . . 97--111
                    S. P. Jukna   Entropy of contact circuits and lower
                                  bounds on their complexity . . . . . . . 113--129
               Jorma Tarhio and   
                   Esko Ukkonen   A greedy approximation algorithm for
                                  constructing shortest common
                                  superstrings . . . . . . . . . . . . . . 131--145
                       W. Kuich   Matrix systems and principal cones of
                                  algebraic power series . . . . . . . . . 147--152
              Wladyslaw Skarbek   Generating ordered trees . . . . . . . . 153--159

Theoretical Computer Science
Volume 57, Number 2--3, May, 1988

                       A. Avron   The semantics and proof theory of linear
                                  logic  . . . . . . . . . . . . . . . . . 161--184
                  L. Pierre and   
                 J.-M. Farinone   Rational index of context-free languages
                                  in $ \exp (\Theta (\sqrt [p]{n})) $ and
                                  $ n^{\Theta ((\ln n)^(1 / p))} $ . . . . 185--204
                     Y. Velinov   An algebraic structure for derivations
                                  in rewriting systems . . . . . . . . . . 205--224
               O. H. Ibarra and   
                      Tao Jiang   Relating the power of cellular arrays to
                                  their closure properties . . . . . . . . 225--238
                 G. Duchamp and   
                   J. Y. Thibon   Transfer theorems for partially
                                  commutative polynomials  . . . . . . . . 239--249
             J.-J. C. Meyer and   
                  E. P. de Vink   Applications of compactness in the Smyth
                                  powerdomain of streams . . . . . . . . . 251--282
                     M. P. Beal   Circular codes, finite automata and
                                  entropy  . . . . . . . . . . . . . . . . 283--302
                  K. Hashiguchi   Notes on congruence relations and factor
                                  pumping conditions for rational
                                  languages  . . . . . . . . . . . . . . . 303--316
                  A. Szalas and   
                 L. Holenderski   Incompleteness of first-order temporal
                                  logic with until . . . . . . . . . . . . 317--325
             J. W. Grossman and   
                  R. S. Zeitman   An inherently iterative computation of
                                  Ackermann's function . . . . . . . . . . 327--330


Theoretical Computer Science
Volume 58, Number 1-3, June, 1988

                  D. Arques and   
                 J. Francon and   
              M. T. Guichet and   
                     P. Guichet   Comparison of algorithms controlling
                                  concurrent access to a database: A
                                  combinatorial approach . . . . . . . . . 3--16
              Amir Averbuch and   
                  Zvi Galil and   
                Shmuel Winograd   Classification of all the minimal
                                  bilinear algorithms for computing the
                                  coefficients of the product of two
                                  polynomials modulo a polynomial. Part I.
                                  The algebra $G[u]/<Q(u)^\ell>,\ell>1$ . . . 17--56
              Allan Borodin and   
              Faith E. Fich and   
Friedhelm Meyer auf der Heide and   
                  Eli Upfal and   
                  Avi Wigderson   A tradeoff between search and update
                                  time for the implicit dictionary problem 57--68
           Franz J. Brandenburg   On the intersection of stacks and queues 69--80
                C. Choffrut and   
  M. P. Schütz\-en\-berger   Counting with rational functions . . . . 81--101
               Clelia De Felice   Finite biprefix sets of paths in a graph 103--128
            Juris Hartmanis and   
            Lane A. Hemachandra   Complexity classes without machines: On
                                  complete languages for UP  . . . . . . . 129--142
        Peter Kirschenhofer and   
               Helmut Prodinger   Further results on digital search trees  143--154
                Sarit Kraus and   
                 Daniel Lehmann   Knowledge, belief and time . . . . . . . 155--174
          Klaus-Jörn Lange   Decompositions of nondeterministic
                                  reductions . . . . . . . . . . . . . . . 175--181
                   Bjorn Lisper   Synthesis and equivalence of concurrent
                                  systems  . . . . . . . . . . . . . . . . 183--199
                    Y. Metivier   On recognizable subsets of free
                                  partially commutative monoids  . . . . . 201--208
                  B. Monien and   
               I. H. Sudborough   Min Cut is NP-complete for edge weighted
                                  trees  . . . . . . . . . . . . . . . . . 209--229
           Jean-Pierre Pecuchet   Etude syntaxique des parties
                                  reconnaissables de mots infinis.
                                  (French) [Syntactic study of rational
                                  omega-languages of infinite words] . . . 231--248
                 G. M. Reed and   
                   A. W. Roscoe   A timed model for communicating
                                  sequential processes . . . . . . . . . . 249--261
            Louis E. Rosier and   
                   Hsu-Chun Yen   On the complexity of deciding fair
                                  termination of probabilistic concurrent
                                  finite-state programs  . . . . . . . . . 263--324
                    Klaus Simon   An improved algorithm for transitive
                                  closure on acyclic digraphs  . . . . . . 325--346
                 Colin Stirling   A generalization of Owicki-Gries's Hoare
                                  logic for a concurrent while language    347--359
               Howard Straubing   Semigroups and languages of dot-depth
                                  two  . . . . . . . . . . . . . . . . . . 361--378
               Peter Varman and   
                  Kshitij Doshi   An efficient parallel algorithm for
                                  updating minimum spanning trees  . . . . 379--397


Theoretical Computer Science
Volume 59, Number 1--2, July, 1988

         Pier Giorgio Bosco and   
           Elio Giovannetti and   
                  Corrado Moiso   Narrowing vs. SLD-resolution . . . . . . 3--23
                  G. Boudol and   
                  I. Castellani   Concurrency and atomicity  . . . . . . . 25--84
          Val Breazu-Tannen and   
                Thierry Coquand   Extensional models for polymorphism  . . 85--114
               M. C. Browne and   
               E. M. Clarke and   
               O. Grümberg   Characterizing finite Kripke structures
                                  in Propositional Temporal Logic  . . . . 115--131
        Wlodzimierz Drabent and   
                Jan Maluszynski   Inductive assertion method for logic
                                  programs . . . . . . . . . . . . . . . . 133--155
                      Y. Lafont   The linear abstract machine  . . . . . . 157--180
      Simona Ronchi Della Rocca   Principal type scheme and unification
                                  for intersection type discipline . . . . 181--209

Theoretical Computer Science
Volume 59, Number 3, August, 1988

               Wim H. Hesselink   Interpretations of recursion under
                                  unbounded nondeterminacy . . . . . . . . 211--234
               Wim H. Hesselink   Deadlock and fairness in morphisms of
                                  transition systems . . . . . . . . . . . 235--257
       A. Scottedward Hodel and   
                Michael C. Loui   Optimal dynamic embedding of $X$-trees
                                  into arrays  . . . . . . . . . . . . . . 259--276
                   K. Kalorkoti   The trace invariant and matrix inversion 277--286
        Manfred Schmidt-Schauss   Implication of clauses is undecidable    287--296
                Wojciech Rytter   On efficient parallel computations for
                                  some dynamic programming problems  . . . 297--307
           Joost Engelfriet and   
                    George Leih   Nonterminal bounded NLC graph grammars   309--315
                Allen Stoughton   Substitution revisited . . . . . . . . . 317--325


Theoretical Computer Science
Volume 60, Number 1, March, 1988

          I. J. Aalbersberg and   
                   G. Rozenberg   Theory of traces . . . . . . . . . . . . 1--82
                  J. Tiuryn and   
                    P. Urzyczyn   Some relationships between logics of
                                  programs and complexity theory . . . . . 83--108

Theoretical Computer Science
Volume 60, Number 2, September, 1988

                 P. America and   
                   J. De Bakker   Designing equivalent semantic models for
                                  process creation . . . . . . . . . . . . 109--176
               A. W. Roscoe and   
                 C. A. R. Hoare   The laws of occam programming  . . . . . 177--229

Theoretical Computer Science
Volume 60, Number 3, December, 1988

         Tali Eilam-Tzoreff and   
                    Uzi Vishkin   Matching patterns in strings subject to
                                  multi-linear transformations . . . . . . 231--254
              Jean-Pierre Duval   Génération d'une section des classes de
                                  conjugaison et arbre des mots de Lyndon
                                  de longueur bornée. (French) [Generation
                                  of a section of conjugation classes and
                                  tree of Lyndon words of limited length]  255--283
                   Arturo Carpi   On synchronizing unambiguous automata    285--296
              Michael J. Beeson   Towards a computation system based on
                                  set theory . . . . . . . . . . . . . . . 297--340
            Jean-Claude Spehner   La reconnaissance des facteurs d'un
                                  langage fini dans un texte en temps
                                  linéaire. (French) [The recognition of
                                  the factors of a finite language in a
                                  text in linear time] . . . . . . . . . . 341--381


Theoretical Computer Science
Volume 61, Number 1, October, 1988

                     J. Shallit   A generalization of automatic sequences  1--16
                  P. Domosi and   
                        Z. Esik   Critical classes for the
                                  $\alpha_0$-product . . . . . . . . . . . 17--24
                      I. Meznik   On a subclass of infinity -regular
                                  languages  . . . . . . . . . . . . . . . 25--32
                         Xin He   A nearly optimal parallel algorithm for
                                  constructing maximal independent set in
                                  planar graphs  . . . . . . . . . . . . . 33--47
                C.-J. Seger and   
               J. A. Brzozowski   An optimistic ternary simulation of gate
                                  races  . . . . . . . . . . . . . . . . . 49--66
            P. M. van den Broek   Comparison of two graph-rewrite systems  67--81
                      S. Thatte   Implementing first-order rewriting with
                                  constructor systems  . . . . . . . . . . 83--92
                    R. Cori and   
                  E. Sopena and   
                 M. Latteux and   
                        Y. Roos   2-asynchronous automata  . . . . . . . . 93--102

Theoretical Computer Science
Volume 61, Number 2--3, November, 1988

             Ronald V. Book and   
                    Ding-Zhu Du   The structure of generalized complexity
                                  cores  . . . . . . . . . . . . . . . . . 103--119
             Elias Dahlhaus and   
                Marek Karpinski   Parallel construction of perfect
                                  matchings and Hamiltonian cycles on
                                  dense graphs . . . . . . . . . . . . . . 121--136
              Tetsuo Moriya and   
                Hideki Yamasaki   Accepting conditions for automata on
                                  $\omega$-languages . . . . . . . . . . . 137--147
                     K. N. King   Alternating multihead finite automata    149--174
       Giuseppe Di Battista and   
               Roberto Tamassia   Algorithms for plane representations of
                                  acyclic digraphs . . . . . . . . . . . . 175--198
                 Jay L. Gischer   The equational theory of pomsets . . . . 199--224
                   Werner Alexi   Extraction and verification of programs
                                  by analysis of formal proofs . . . . . . 225--258
              George Gargov and   
                  Solomon Passy   Determinism and looping in combinatory
                                  PDL  . . . . . . . . . . . . . . . . . . 259--277
                 Ludwig Staiger   Ein Satz über die Entropie von
                                  Untermonoiden. (German) [A theorem on
                                  the entropy of submonoids] . . . . . . . 279--282
              Thomas Kretschmer   A closure property of regular languages  283--287
                   Andre Arnold   Logical definability of fixed points . . 289--297
               Edward G. Belaga   Bilinear mincing rank  . . . . . . . . . 299--306
             Nimrod Megiddo and   
                    Uzi Vishkin   On finding a minimum dominating set in a
                                  tournament . . . . . . . . . . . . . . . 307--316
                    R. Kennaway   On 'On graph rewritings' . . . . . . . . 317--320


Theoretical Computer Science
Volume 62, Number 1--2, December, 1988

            Serge Abiteboul and   
                        R. Hull   Restructuring hierarchical database
                                  objects  . . . . . . . . . . . . . . . . 3--38
               Paolo Atzeni and   
                D. Stott Parker   Set containment inference and syllogisms 39--65
          Edward P. F. Chan and   
            Hector J. Hernandez   On the desirability of $\gamma$-acyclic
                                  BCNF database schemes  . . . . . . . . . 67--104
               V. S. Lakshmanan   Split-freedom and MVD-intersection: A
                                  new characterization of multivalued
                                  dependencies having conflict-free covers 105--122
                Nancy Lynch and   
                Michael Merritt   Introduction to the theory of nested
                                  transactions . . . . . . . . . . . . . . 123--185
             Domenico Sacca and   
                  Carlo Zaniolo   The generalized counting method for
                                  recursive logic queries  . . . . . . . . 187--220
                 Dirk van Gucht   Interaction-free multivalued dependency
                                  sets . . . . . . . . . . . . . . . . . . 221--233

Theoretical Computer Science
Volume 62, Number 3, December, 1988

                 Viliam Geffert   A representation of a recursively
                                  enumerable languages by two
                                  homomorphisms and a quotient . . . . . . 235--249
        Nageswara S. V. Rao and   
              S. S. Iyengar and   
                  R. L. Kashyap   An average-case analysis of MAT and
                                  inverted file  . . . . . . . . . . . . . 251--266
                    Kai Salomaa   A pumping result for $2$-context-free
                                  languages  . . . . . . . . . . . . . . . 267--287
                Thomas Zeugmann   On the Power of Recursive Optimizers . . 289--310
             Samuel R. Buss and   
                   Gyorgy Turan   Resolution proofs on generalized
                                  pigeonhole principles  . . . . . . . . . 311--317
               Christoph Meinel   The power of nondeterminism in
                                  polynomial-size bounded-width branching
                                  programs . . . . . . . . . . . . . . . . 319--325


Theoretical Computer Science
Volume 63, Number 1, January, 1989

                 Ursula Schmidt   Avoidable patterns on two letters  . . . 1--17
                     M. Livesey   Stable families of behavioural
                                  equivalences . . . . . . . . . . . . . . 19--41
              Klaus Ambos-Spies   On the relative complexity of hard
                                  problems for complexity classes without
                                  complete problems  . . . . . . . . . . . 43--61
           Seymour Ginsburg and   
                 Chang-jie Tang   Cohesion of object histories . . . . . . 63--90
              J. Howard Johnson   A unified framework for disambiguating
                                  finite transductions . . . . . . . . . . 91--111

Theoretical Computer Science
Volume 63, Number 2, February, 1989

                  Masami Hagiya   Generalization from partial
                                  parametrization in higher-order type
                                  theory . . . . . . . . . . . . . . . . . 113--139
            Jean-Camille Birget   Concatenation of inputs in a two-way
                                  automaton  . . . . . . . . . . . . . . . 141--156
               Clelia de Felice   Construction of a family of finite
                                  maximal codes  . . . . . . . . . . . . . 157--184
                   Andrzej Pelc   Searching with known error probability   185--202
                Juraj Hromkovic   Tradeoffs for language recognition on
                                  alternating machines . . . . . . . . . . 203--221
              Takashi Saito and   
              Hidenosuke Nishio   Structural and behavioral equivalence
                                  relations in automata networks . . . . . 223--237

Theoretical Computer Science
Volume 63, Number 3, March, 1989

                Ding-Zhu Du and   
                 Ronald V. Book   On inefficient special cases of
                                  NP-complete problems . . . . . . . . . . 239--252
           Georges Gardarin and   
           Irene Guessarian and   
     Christophe de Maindreville   Translation of logic programs into
                                  functional fixpoint equations  . . . . . 253--274
            David B. Benson and   
                   Jerzy Tiuryn   Fixed points in free process algebras,
                                  part I . . . . . . . . . . . . . . . . . 275--294
                 Andrzej Lingas   Subgraph isomorphism for biconnected
                                  outerplanar graphs in cubic time . . . . 295--302
           Stephen L. Bloom and   
                    Zoltan Esik   Equational logic of circular data type
                                  specification  . . . . . . . . . . . . . 303--331
               Aldo de Luca and   
             Stefano Varricchio   Some combinatorial properties of the
                                  Thue--Morse sequence and a problem in
                                  semigroups . . . . . . . . . . . . . . . 333--348


Theoretical Computer Science
Volume 64, Number 1, April, 1989

           Hans-Jörg Stoss   On the representation of rational
                                  functions of bounded complexity  . . . . 1--13
           Hans-Jörg Stoss   Lower bounds for the complexity of
                                  polynomials  . . . . . . . . . . . . . . 15--23
                 K. Jojczyk and   
               J. Konieczny and   
                       T. Kuzak   On interleaving behaviour of PT-nets . . 25--38
              Etsuji Tomita and   
                  Kazushi Seino   A direct branching algorithm for
                                  checking the equivalence of two
                                  deterministic pushdown transducers, one
                                  of which is real-time strict . . . . . . 39--53
                  Hiroyuki Sato   E-CCC: between CCC and TOPOS . . . . . . 55--66
              Dang Van Hung and   
                     Elod Knuth   Semi-commutations and Petri nets . . . . 67--81
                 Eli Shamir and   
                 Assaf Schuster   Communication aspects of networks based
                                  on geometric incidence relations . . . . 83--96
               J. Roger Hindley   BCK-combinators and linear
                                  \$lambda@-terms have types . . . . . . . 97--105
                  Zvi Galil and   
             Raffaele Giancarlo   Speeding up dynamic programming with
                                  applications to molecular biology  . . . 107--118
              Marco Protasi and   
                Maurizio Talamo   On the number of arithmetical operations
                                  for finding Fibonacci numbers  . . . . . 119--124
                  E. Korach and   
                   S. Moran and   
                        S. Zaks   Optimal lower bounds for some
                                  distributed algorithms for a complete
                                  network of processors  . . . . . . . . . 125--132

Theoretical Computer Science
Volume 64, Number 2, May 7, 1989

           Clyde P. Kruskal and   
              Larry Rudolph and   
                      Marc Snir   Techniques for parallel manipulation of
                                  sparse matrices  . . . . . . . . . . . . 135--157
                Yves Robert and   
                 Denis Trystram   Optimal scheduling algorithms for
                                  parallel Gaussian elimination  . . . . . 159--173
                    Gordon Lyon   Design factors for parallel processing
                                  benchmarks . . . . . . . . . . . . . . . 175--189
              J. C. Bermond and   
                 J. M. Fourneau   Independent connections: An easy
                                  characterization of baseline-equivalent
                                  multistage interconnection networks  . . 191--201
             I. F. Akyildiz and   
                   H. von Brand   Exact solutions for open, closed and
                                  mixed queueing networks with rejection
                                  blocking . . . . . . . . . . . . . . . . 203--219

Theoretical Computer Science
Volume 64, Number 3, May 29, 1989

                Eugene W. Stark   Concurrent transition systems  . . . . . 221--269
                  Denis Therien   Programs over aperiodic monoids  . . . . 271--280
        Antoni Mazurkiewicz and   
           Edward Ochmanski and   
               Wojciech Penczek   Concurrent systems and inevitability . . 281--304
           Rodney R. Howell and   
                Louis E. Rosier   Problems concerning fairness and
                                  temporal logic for conflict-free Petri
                                  nets . . . . . . . . . . . . . . . . . . 305--329
                  Noga Alon and   
                      Uri Zwick   On Neciporuk's theorem for branching
                                  programs . . . . . . . . . . . . . . . . 331--342
    Hans Kleine Büning and   
           Theodor Lettmann and   
                  Ernst W. Mayr   Projections of vector addition system
                                  reachability sets are semilinear . . . . 343--350


Theoretical Computer Science
Volume 65, Number 1, June 15, 1989

          Patrice Enjalbert and   
         Luis Farinas del Cerro   Modal resolution in clausal form . . . . 1--33
                   Martin Abadi   The power of temporal proofs . . . . . . 35--83
               Satish R. Thatte   Full abstraction and limiting
                                  completeness in equational languages . . 85--119

Theoretical Computer Science
Volume 65, Number 2, June 28, 1989

                      Anonymous   Conference on Arithmetics and Coding
                                  Systems  . . . . . . . . . . . . . . . . ??
             Jean-Paul Allouche   On a sequence of rational functions  . . 123--130
                   F. Blanchard   \$beta@-expansions and symbolic dynamics 131--141
       Noelle Bleuzen-Guernalec   On a possible classification of
                                  real-time constructed sequences  . . . . 143--148
                  F. M. Dekking   On the probability of occurrence of
                                  labelled subtrees of a randomly labelled
                                  tree . . . . . . . . . . . . . . . . . . 149--152
               J.-M. Dumont and   
                   Alain Thomas   Systémes de num\-é\-ra\-tion et fonction
                                  fractales relatifs aux substitutions.
                                  (French) [Systems of numeration and
                                  fractal functions relative to
                                  substitutions] . . . . . . . . . . . . . 153--169
                  G. Hansel and   
                      D. Perrin   Rational probability measures  . . . . . 171--188
              P. Hellekalek and   
                     G. Larcher   On Weyl sums and skew products over
                                  irrational rotations . . . . . . . . . . 189--196
                  Cor Kraaikamp   Statistic and ergodic properties of
                                  Minkowski's diagonal continued fraction  197--212
           M. Mendes France and   
          A. J. van der Poorten   From geometry to Euler identities  . . . 213--220
                Filippo Mignosi   Infinite words with linear subword
                                  complexity . . . . . . . . . . . . . . . 221--242
                    Makoto Mori   On the Fredholm determinant of a
                                  piecewise linear transformation  . . . . 243--248
                 Brigitte Mosse   Q-Adic spectral analysis of some
                                  arithmetic sequences . . . . . . . . . . 249--263
                Antonio Restivo   Finitely generated sofic systems . . . . 265--270

Theoretical Computer Science
Volume 65, Number 3, July 17, 1989

              Hirofumi Yokouchi   Church--Rosser theorem for a rewriting
                                  system on categorical combinators  . . . 271--290
                 Therese Hardin   Confluence results for the pure strong
                                  categorical logic CCL \$lambda@-calculi
                                  as subsystems of {CCL} . . . . . . . . . 291--342
              J. C. Shepherdson   A sound and complete semantics for a
                                  version of negation as failure . . . . . 343--371


Theoretical Computer Science
Volume 66, Number 1, August 2, 1989

                T. Lehmkuhl and   
                    T. Lickteig   On the order of approximation in
                                  approximative triadic decompositions of
                                  tensors  . . . . . . . . . . . . . . . . 1--14
                    P. E. Dunne   On monotone simulations of nonmonotone
                                  networks . . . . . . . . . . . . . . . . 15--25
                     A. Piperno   Abstraction problems in combinatory
                                  logic: a compositive approach  . . . . . 27--43
                        J. Kari   Observations concerning a public-key
                                  cryptosystem based on iterated morphisms 45--53
                  Zhang Luo Xin   An efficient algorithm to decide whether
                                  a monoid presented by a regular
                                  Church--Rosser Thue system is a group    55--63
                R. op den Akker   On LC(0) grammars and languages  . . . . 65--85
                    A. Urquhart   The complexity of Gentzen systems for
                                  propositional logic  . . . . . . . . . . 87--97
                     R. Statman   On sets of solutions to combinator
                                  equations  . . . . . . . . . . . . . . . 99--104
                        A. Pelc   Weakly adaptive comparison searching . . 105--111
                     D. Mundici   Functions computed by monotone Boolean
                                  formulas with no repeated variables  . . 113--114

Theoretical Computer Science
Volume 66, Number 2, August 20, 1989

                 Volker Diekert   On the Knuth--Bendix completion for
                                  concurrent processes . . . . . . . . . . 117--136
          Martin Dietzfelbinger   Lower bounds for sorting of sums . . . . 137--155
       Herbert Edelsbrunner and   
               Guenter Rote and   
                     Ermo Welzl   Testing the necklace condition for
                                  shortest tours and optimal factors in
                                  the plane  . . . . . . . . . . . . . . . 157--180
       Christos Levcopoulos and   
             Andrzej Lingas and   
                Jorg-R. R. Sack   Heuristics for optimum binary search
                                  trees and minimum weight triangulation
                                  problems . . . . . . . . . . . . . . . . 181--203
            M. A. Nait Abdallah   A logico-algebraic approach to the model
                                  theory of knowledge  . . . . . . . . . . 205--232

Theoretical Computer Science
Volume 66, Number 3, August 26, 1989

                        P. Weil   Inverse monoids of dot-depth two . . . . 233--245
                    H. Yamasaki   Language-theoretical representations of
                                  $Gw$-languages . . . . . . . . . . . . . 247--254
                 D. Angluin and   
              W. I. Gasarch and   
                    C. H. Smith   Training sequences . . . . . . . . . . . 255--272
                     A. Ito and   
                   K. Inoue and   
                    I. Takanami   Deterministic two-dimensional on-line
                                  tessellation acceptors are equivalent to
                                  two-way two-dimensional alternating
                                  finite automata through 180
                                  degrees-rotation . . . . . . . . . . . . 273--287
                G. Jacopini and   
                   P. Mentrasti   Generation of invertible functions . . . 289--297
             J. A. Makowsky and   
                        I. Sain   Weak second order characterizations of
                                  various program verification systems . . 299--321
                   M. Mezghiche   On pseudo-c beta normal form in
                                  combinatory logic  . . . . . . . . . . . 323--331
                     M. Tiomkin   Probabilistic termination versus fair
                                  termination  . . . . . . . . . . . . . . 333--340
                     J. Honkala   A necessary condition for the
                                  rationality of the zeta function of a
                                  regular language . . . . . . . . . . . . 341--347


Theoretical Computer Science
Volume 67, Number 1, September 5, 1989

              Charles Swart and   
                  Dana Richards   On the inference of strategies . . . . . 5--18
                 Friedrich Otto   On deciding confluence of finite
                                  string-rewriting systems modulo partial
                                  commutativity  . . . . . . . . . . . . . 19--35
                  Ursula Martin   A geometrical approach to multiset
                                  orderings  . . . . . . . . . . . . . . . 37--54
                Michael Clausen   Fast generalized Fourier transforms  . . 55--63
              Daniele Beauquier   Minimal automation for a factorial,
                                  transitive, and rational language  . . . 65--73
                  Etsuro Moriya   A grammatical characterization of
                                  alternating pushdown automata  . . . . . 75--85
                G. Marongiu and   
                    S. Tulipani   On a conjecture of Bergstra and Tucker   87--97
             Katsushi Inoue and   
             Itsuo Takanami and   
                Juraj Hromkovic   Leaf-size hierarchy of two-dimensional
                                  alternating Turing machines  . . . . . . 99--110
             Dana Pardubska and   
              Ivana Stefanekova   Nondeterministic multicounter machines
                                  and complementation  . . . . . . . . . . 111--113
                 M. Cosnard and   
                  J. Duprat and   
                    A. Ferreira   Complexity of selection in X + Y . . . . 115--120
              Catherine Petuaud   Entropie topologique des syst\`emes
                                  specifiés. (French) [Topological entropy
                                  of specified systems]  . . . . . . . . . 121--128
               Ramon Pino Perez   Decidability of the restriction
                                  equational theory in the partial lambda
                                  calculus . . . . . . . . . . . . . . . . 129--139

Theoretical Computer Science
Volume 67, Number 2--3, October 3, 1989

                K. Madlener and   
                        F. Otto   About the descriptive power of certain
                                  classes of finite string-rewriting
                                  systems  . . . . . . . . . . . . . . . . 143--172
                L. Bachmair and   
                  N. Dershowitz   Completion for rewriting modulo a
                                  congruence . . . . . . . . . . . . . . . 173--201
              J. H. Gallier and   
                      W. Snyder   Complete sets of transformations for
                                  general E-unification  . . . . . . . . . 203--260
                  C. Choppy and   
                  S. Kaplan and   
                       M. Soria   Complexity analysis of term-rewriting
                                  systems  . . . . . . . . . . . . . . . . 261--282
            J. C. M. Baeten and   
             J. A. Bergstra and   
                 J. W. Klop and   
                 W. P. Weijland   Term-rewriting systems with rule
                                  priorities . . . . . . . . . . . . . . . 283--301
                    H. Kirchner   Schematization of infinite sets of
                                  rewrite rules generated by divergent
                                  completion processes . . . . . . . . . . 303--332


Theoretical Computer Science
Volume 68, Number 1, October 16, 1989

           P. Kirschenhofer and   
               H. Prodinger and   
                 W. Szpankowski   On the balance property of Patricia
                                  trees: external path length viewpoint    1--17
                J. H. Chang and   
               O. H. Ibarra and   
                    M. A. Palis   Efficient simulations of simple models
                                  of parallel computation by time-bounded
                                  ATMs and space-bounded TMs . . . . . . . 19--36
                      M. Droste   Event structures and domains . . . . . . 37--47
                       G. Hofer   Left ideals and reachability in machines 49--56
                 G. Gambosi and   
             G. F. Italiano and   
                      M. Talamo   Worst-case analysis of the set-union
                                  problem with extended backtracking . . . 57--70
                  U. Huckenbeck   Euclidian geometry in terms of automata
                                  theory . . . . . . . . . . . . . . . . . 71--87
                  H. J. Karloff   An NC algorithm for Brooks' theorem  . . 89--103
                  M. B. Josephs   The semantics of lazy functional
                                  languages  . . . . . . . . . . . . . . . 105--111
                  B. S. Chlebus   A hierarchy of propositional Horn
                                  formulas . . . . . . . . . . . . . . . . 113--119

Theoretical Computer Science
Volume 68, Number 2, October 30, 1989

                  V. Arvind and   
                      S. Biswas   On some bandwidth restricted versions of
                                  the satisfiability problem of
                                  propositional CNF formulas . . . . . . . 123--134
                H. A. Blair and   
             V. S. Subrahmanian   Paraconsistent logic programming . . . . 135--154
                  A. Lingas and   
                A. Proskurowski   On parallel complexity of the subgraph
                                  homeomorphism and the subgraph
                                  isomorphism problem for classes of
                                  planar graphs  . . . . . . . . . . . . . 155--173
                      J. Parrow   Submodule construction as equation
                                  solving in CCS . . . . . . . . . . . . . 175--202
                   R. Ramanujam   Semantics of distributed definite clause
                                  programs . . . . . . . . . . . . . . . . 203--220

Theoretical Computer Science
Volume 68, Number 3, November 12, 1989

                     T. Coquand   Categories of embeddings . . . . . . . . 221--237
                     R. Gutbrod   A transformation system for generating
                                  description languages of chain code
                                  pictures . . . . . . . . . . . . . . . . 239--252
                   F. Blanchard   Certain sofic systems engendered codes   253--265
                N. Immerman and   
                  S. R. Mahaney   Relativizing relativized computations    267--276
     M. T. Hortala-Gonzalez and   
          M. Rodriguez-Artalejo   Hoare's logic for nondeterministic
                                  regular programs: a nonstandard approach 277--302
                      F. Bracho   Continuously generated fixed points  . . 303--317
               P. Narendran and   
                        F. Otto   Some polynomial-time algorithms for
                                  finite monadic Church--Rosser Thue
                                  systems  . . . . . . . . . . . . . . . . 319--332
                     U. Solitro   A typed calculus based on a fragment of
                                  linear logic . . . . . . . . . . . . . . 333--342
                   E. Gafni and   
                    J. Naor and   
                       P. Ragde   On separating the EREW and CREW PRAM
                                  models . . . . . . . . . . . . . . . . . 343--346
                   C. P. Rupert   Comment on a remark of Forys . . . . . . 347--348


Theoretical Computer Science
Volume 69, Number 1, December 5, 1989

                     L. Vieille   Recursive query processing: the power of
                                  logic  . . . . . . . . . . . . . . . . . 1--53
                  J.-M. Kerisit   A relational approach to logic
                                  programming: the extended Alexander
                                  method . . . . . . . . . . . . . . . . . 55--68
                      S. Kaplan   Algebraic specification of concurrent
                                  systems  . . . . . . . . . . . . . . . . 69--115

Theoretical Computer Science
Volume 69, Number 2, December 11, 1989

                     F. Nielson   Two-level semantics and abstract
                                  interpretation . . . . . . . . . . . . . 117--242

Theoretical Computer Science
Volume 69, Number 3, December 18, 1989

               M. Felleisen and   
                 D. P. Friedman   A syntactic theory of sequential state   243--287
                M. Falaschi and   
                    G. Levi and   
             C. Palamidessi and   
                    M. Martelli   Declarative modeling of the operational
                                  behavior of logic languages  . . . . . . 289--318
                K. A. Baker and   
              G. F. McNulty and   
                      W. Taylor   Growth problems for avoidable words  . . 319--345


Theoretical Computer Science
Volume 302, Number 1--3, June 13, 2003

                  Marek Chrobak   Errata to: ``Finite Automata and Unary
                                  Languages'': [Theoret. Comput. Sci. 47
                                  (1986) 149--158] . . . . . . . . . . . . 497--498