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

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