Theoretical Computer Science, Volume 63

Volume 63, Number 1, 1989

Ursula Schmidt: Avoidable Patterns on Two Letters. 1-17
Mike 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, Chang-jie Tang: Cohesion of Object Histories. 63-90
J. Howard Johnson: A Unified Framework for Disambiguating Finite Transductions. 91-111

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, Hidenosuke Nishio: Structural and Behavioral Equivalence Relations in Automata Networks. 223-237

Ding-Zhu Du, Ronald V. Book: On Inefficient Special Cases of NP-Complete Problems. 239-252
Georges Gardarin, Irène Guessarian, Christophe de Maindreville: Translation of Logic Programs into Functional Fixpoint Equations. 253-274
David B. Benson, 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, Zoltán Ésik: Equational Logic of Circular Data Type Specification. 303-331
Aldo de Luca, Stefano Varricchio: Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups. 333-348