Theory of Computing Systems, Volume 30

Volume 30, Number 1, January/February 1997

• Paul G. Spirakis: Editor's Foreword. 1 BibTeX
• Andrea Pietracaprina, Franco P. Preparata: Practical Constructive Schemes for Deterministic Shared-Memory Access. 3-37 BibTeX
• Christos Kaklamanis, Danny Krizanc, Satish Rao: New Graph Decompositions with Applications to Emulations. 39-49 BibTeX
• Lenwood S. Heath: Graph Embeddings and Simplicial Maps. 51-65 BibTeX
• James Haralambides, Fillia Makedon: Approximation Algorithms for the Bandwidth Minimization Problem for a Large Class of Trees. 67-90 BibTeX
• Ioan I. Macarie: Multihead Two-Way Probabilistic Finite Automata. 91-109 BibTeX

Volume 30, Number 2, March/April 1997

• Moti Frances, Ami Litman: On Covering Problems of Codes. 113-119 BibTeX
• Nicholas Pippenger: Regular Languages and Stone Duality. 121-134 BibTeX
• Hans-Jörg Burtschick, W. Lindner: On Sets Turing Reducible to p-Selective Sets. 135-143 BibTeX
• Violet R. Syrotiuk, Charles J. Colbourn, Jan K. Pachl: Wang Tilings and Distributed Verification on Anonymous Torus Networks. 145-163 BibTeX
• Patrizio Cintioli, Riccardo Silvestri: Helping by Unambiguous Computation and Probabilistic Computation. 165-180 BibTeX
• Kazuyuki Amano, Akira Maruoka: Approximation Algorithms for DNF Under Distributions with Limited Independence. 181-196 BibTeX
• F. Point, Véronique Bruyère: On the Cobham-Semenov Theorem. 197-220 BibTeX

Volume 30, Number 3, May/June 1997

• Eric Goles Ch., Martín Matamala: Reaction-Diffusion Automata: Three States Implies Universality. 223-229 BibTeX
• Andrea Pietracaprina, Geppino Pucci: The Complexity of Deterministic PRAM Simulation on Distributed Memory Machines. 231-247 BibTeX
• Vijay V. Raghavan, Dawn Wilkins: A Characterization and Nearly Linear-Time Equivalence Test for µ-Branching Programs. 249-283 BibTeX
• Jean-Paul Allouche, E. Cateland, W. J. Gilbert, Heinz-Otto Peitgen, Jeffrey Shallit, Guentcho Skordev: Automatic Maps in Exotic Numeration System. 285-331 BibTeX

Volume 30, Number 4, July/August 1997

• Hendrik Jan Hoogeboom, Paulien ten Pas: Monadic Second-Order Definable Text Languages. 335-354 BibTeX
• Carsten Damm, Markus Holzer, Peter Rossmanith: Expressing Uniformity via Oracles. 355-366 BibTeX
• Luis B. Morales: Diagonal Polynomials and Diagonal Orders on Multidimensional Lattices. 367-382 BibTeX
• Jean-Eric Pin, Pascal Weil: Ponynominal Closure and Unambiguous Product. 383-422 BibTeX
• Uwe Schöning: Complexity of Presburger Arithmetic with Fixed Quantifier Dimension. 423-428 BibTeX
• Jack H. Lutz: Observations on Measure and Lowness for \Delta^p_2. 429-442 BibTeX

Volume 30, Number 5, September/October 1997

• Shimon Even, Sergio Rajsbaum: The Use of a Synchronizer Yields the Maximum Computation Rate in Distributed Networks. 447-474 BibTeX
• Hsu-Chun Yen, Bow-Yaw Wang, Ming-Sheng Yang: Deciding a Class of Path Formulas for Conflict-Free Petri Nets. 475-494 BibTeX
• Christoph Meinel, Anna Slobodová: A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams. 495-518 BibTeX

Volume 30, Number 6, November/December 1997

• Gianfranco Bilardi, Franco P. Preparata: Processor-Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds. 523-546 BibTeX
• Frank K. H. A. Dehne, Xiaotie Deng, Patrick W. Dymond, Andreas Fabri, Ashfaq A. Khokhar: A Randomized Parallel Three-Dimensional Convex Hull Algorithm for Coarse-Grained Multicomputers. 547-558 BibTeX
• Frank Thomson Leighton, Yuan Ma, Torsten Suel: On Probabilistic Networks for Selection, Merging, and Sorting. 559-582 BibTeX
• Charles E. Leiserson, Keith H. Randall: Parallel Algorithms for the Circuit Value Update Problem. 583-597 BibTeX
• Philip D. MacKenzie: Lower Bounds for Randomized Exclusive Write PRAMs. 599-626 BibTeX
• Friedhelm Meyer auf der Heide, Martin Storch, Rolf Wanka: Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks. 627-644 BibTeX
• Nir Shavit, Dan Touitou: Elimination Trees and the Construction of Pools and Stacks. 645-670 BibTeX