THEORETICAL COMPUTER SCIENCE Algorithms, automata, complexity and games VOLUME 158, NUMBERS 1-2, 20 MAY 1996 Abstracted/Indexed in: ACM Computing Reviews, Compuscience, Computer Abstracts, Current Contents: Engineering, Technology & Applied Science, Engineering Index/Com- pendex, INSPEC Information Services, Mathematical Reviews, Zentralblatt fur Mathematik CONTENTS J. Gabarro, C. Martinez and X. Messeguer A design of a parallel dictionary using skip lists M. Koskas About the p-paperfolding words A. Ferreira and M. Grammatikakis Randomized routing on generalized hypercubes S. Fabre Dépendance de systémes de numeration associés a des puissances d’un nombre de Pisot N. Jonoska Sofic shifts with synchronizing presentations M. Demange and V.Th. Paschos On an approximation measure founded on the links between optimization and polynomial approximation theory Y. Hirshfeld, M. Jerrum and F. Moller A polynomial algorithm for deciding bisimilarity of normed context-free processes T.Y. Nishida and A. Salomaa Slender OL languages D. Breslauer Saving comparisons in the Crochemore-Perrin string matching algorithm M. Agrawal and V. Arvind Geometric sets of low information content S.E. Mocas Separating classes in the exponential time hierarchy from classes in PH G. Ramalingam and T. Reps On the computational complexity of dynamic graph problems Y. Takahashi Solving optimization problems with variable-constraint by an extended Cohen-Grossberg model MATHEMATICAL GAMES U. Zwick and M.S. Paterson The complexity of mean payoff games on graphs NOTES M. Agrawal and V. Arvind Quasi-linear truth-table reductions to p-selective sets S. Burckel Closed iterative calculus Contents EATCS Bulletin Number 58 Author Index Volume 158