Theoretical Computer Science, Volume 68

Volume 68, Number 1, 1989

Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski: On the Balance Property of Patricia Tries: External Path Length Viewpoint. 1-17
Jik H. Chang, Oscar H. Ibarra, Michael A. Palis: Efficient Simulations of Simple Models of Parallel Computation by Time-Bounded ATMs and Space-Bounded TMs. 19-36
Manfred Droste: Event Structures and Domains. 37-47
Gerhard Hofer: Left Ideals and Reachability in Machines. 49-56
Giorgio Gambosi, Giuseppe F. Italiano, Maurizio Talamo: Worst-Case Analysis of the Set-Union Problem with Extended Backtracking. 57-70
Ulrich Huckenbeck: Euclidian Geometry in Terms of Automata Theory. 71-87
Howard J. Karloff: An NC Algorithm for Brooks' Theorem. 89-103
Mark B. Josephs: The Semantics of Lazy Functional Languages. 105-111
Bogdan S. Chlebus: A Hierarchy of Propositional Horn Formulas. 113-119

Vikraman Arvind, Somenath Biswas: On Some Bandwidth Restricted Versions of the Satisfiability Problem of Propositional CNF Formulas. 123-134
Howard A. Blair, V. S. Subrahmanian: Paraconsistent Logic Programming. 135-154
Andrzej Lingas, Andrzej Proskurowski: On Parallel Complexity of the Subgraph Homeomorphism and the Subgraph Isomorphism Problem for Classes of Planar Graphs. 155-173
Joachim Parrow: Submodule Construction as Equation Solving in CCS. 175-202
Ramaswamy Ramanujam: Semantics of Distributed Definite Clause Programs. 203-220

Thierry Coquand: Categories of Embeddings. 221-237
Roger Gutbrod: A Transformation System for Generating Description Languages of Chain Code Pictures. 239-252
François Blanchard: Codes Engendrant Certains Systemes Sofiques. 253-265
Neil Immerman, Stephen R. Mahaney: Relativizing Relativized Computations. 267-276
Maria Teresa Hortalá-González, Mario Rodríguez-Artalejo: Hoare's Logic for Nondeterministic Regular Programs: A Nonstandard Approach. 277-302
Felipe Bracho: Continously Generated Fixed Points. 303-317
Paliath Narendran, Friedrich Otto: Some Polynomial-Time Algorithms for Finite Monadic Church-Rosser Thue Systems. 319-332
Ugo Solitro: A Typed Calculuc Based on a Fragment of Linear Logic. 333-342
Eli Gafni, Joseph Naor, Prabhakar Ragde: On Separating the Erew and Crew Pram Models. 343-346