Theoretical Computer Science, Volume 81

Volume 81, Number 1, 1991

Zoltán Fülöp, Sándor Vágvölgyi: A Complete Classification of Deterministic Root-To-Frontier Tree Transformation Classes. 1-15
Jean-Marie Boë: Les Boîtes. 17-34
Shouwen Tang, Ronald V. Book: Polynomial-Time Reducibilities and ``Almost All'' Oracle Sets. 35-47
Olivier Dubois: Counting the Number of Solutions for Instances of Satisfiability. 49-64
Olivier Dubois, Jacques Carlier: Probabilistic approach to the Satisfiability Problem. 65-75
Marek Piotrów: On the Complexity of Counting in the Polynomial Hierarchy. 77-95
Amihood Amir, Gad M. Landau: Fast Parallel and Serial Multidimensional Aproximate Array Matching. 97-115
Frantisek Matús: Abstract Functional Dependency Structures. 117-126
Jack H. Lutz: An Upward Measure Separation Theorem. 127-135
Hing Leung: Limitedness Theorem on Finite Automata with Distance Functions: An Algebraic Proof. 137-145
Robert Cori, Maria Rosaria Formisano: On the Number of Partially Abelian Square-Free Words on a Three-Letter Alphabet. 147-153
Juris Hartmanis, Lane A. Hemachandra: One-Way Functions and the Nonisomorphism of NP-Complete Sets. 155-163

Deepak Kapur, David R. Musser, Paliath Narendran, Jonathan Stillman: Semi-Unification. 169-187
Sanjeev N. Khadilkar, Somenath Biswas: Padding, Commitment and Self-Reducibility. 189-199
Keshav Pingali, Kattamuri Ekanadham: Accumulators: New Logic Variable Abstractions for Functional Languages. 201-221
K. S. H. S. R. Bhatta, Harish Karnick: A Resolution Rule for Well-Formed Formulae. 223-235
Hans L. Bodlaender: New Lower Bound Techniques for Distributed Leader Finding and Other Problems on Rings of Processors. 237-256
Katja Lenz, Ingo Wegener: The Conjunctive Complexity of Quadratic Boolean Functions. 257-268
Peter R. J. Asveld: Abstract Grammars Based on Transductions. 269-288
Jürgen Dassow: On the Connectedness of Pictures in Chain Code Picture Languages. 289-294
To-Yat Cheung, Yun-zhou Zhu: Recognizing Different Types of Beta-Cycles in a Database Scheme. 295-304
Erzsébet Csuhaj-Varjú, Jozef Kelemen: On the Power of Cooperation: A Regular Representation of Recursively Enumerable Languages. 305-310
Michal Chytil, Maxime Crochemore, Burkhard Monien, Wojciech Rytter: On the Parallel Recognition of Unambiguous Context-Free Languages. 311-316
Nimrod Megiddo, Christos H. Papadimitriou: On Total Functions, Existence Theorems and Computational Complexity. 317-324