Theoretical Computer Science, Volume 84

Volume 84, Number 1, 1991

Danièle Beauquier, Jean-Eric Pin: Languages and Scanners. 3-21
Gilles Brassard, Claude Crépeau, Moti Yung: Constant-Round Perfect Zero-Knowledge Computationally Convincing Protocols. 23-52
Véronique Bruyère: Maximal Codes With Bounded Deciphering Delay. 53-76
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir: A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications. 77-105
Giorgio Gambosi, Enrico Nardelli, Maurizio Talamo: A Pointer-Free Data Structure for Merging Heaps and Min-Max Heaps. 107-126
Christos H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. 127-150

Michael Clausen, Andreas W. M. Dress, Johannes Grabmeier, Marek Karpinski: On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. 151-164
Ahmed Saoudi: Generalized Automata on Infinite Trees and Muller-McNaughton's Theorem. 165-177
Shlomo Moran, Yaron Wolfsthal: Optimal Covering of Cacti by Vertex-Disjoint Paths. 179-197
Richard Beigel: Bounded Queries to SAT and the Boolean Hierarchy. 199-223
Bernd Becker, Uwe Sparmann: Computations over Finite Monoids and their Test Complexity. 225-250
C. P. Rupert: Which Kleene Semigroups are Finite? 251-264
Hermann A. Maurer, Arto Salomaa, Derick Wood: Bounded Delay L Codes. 265-279
Jürgen Dassow, Helmut Jürgensen: Deterministic Soliton Automata with a Single Exterior Node. 281-292
William A. Baldwin, George O. Strawn: Multidimensional Trees. 293-311