Theory of Computing Systems, Volume 30

Volume 30, Number 1, January/February 1997

ACM Symposium on Parallel Algorithms and Architectures

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

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

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

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

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

ACM Symposium on Parallel Algorithms and Architectures

Gianfranco Bilardi, Franco P. Preparata:
Processor-Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds. 523-546
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
Frank Thomson Leighton, Yuan Ma, Torsten Suel:
On Probabilistic Networks for Selection, Merging, and Sorting. 559-582
Charles E. Leiserson, Keith H. Randall:
Parallel Algorithms for the Circuit Value Update Problem. 583-597
Philip D. MacKenzie:
Lower Bounds for Randomized Exclusive Write PRAMs. 599-626
Friedhelm Meyer auf der Heide, Martin Storch, Rolf Wanka:
Optimal Tradeoffs Between Size and Slowdown for Universal Parallel Networks. 627-644
Nir Shavit, Dan Touitou:
Elimination Trees and the Construction of Pools and Stacks. 645-670

Last update Sat May 18 20:47:29 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page