Theory of Computing Systems, Volume 35

Volume 35, Number 1, 2002

Amir M. Ben-Amram, Holger Petersen:
Improved Bounds for Functions Related to Busy Beavers. 1-11
Pierre B. A. Lecomte, Michel Rigo:
On the Representation of Real Numbers Using Regular Languages. 13-38
Palash Sarkar, Subhamoy Maitra:
Cross-Correlation Analysis of Cryptographically Useful Boolean Functions and S-Boxes. 39-57
Jung-Sheng Fu, Gen-Huey Chen:
Hamiltonicity of the Hierarchical Cubic Network. 59-79
André Große, Jörg Rothe, Gerd Wechsung:
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones. 81-93

Vijaya Ramachandran, Ramesh K. Sitaraman:
SPAA 1999 - Guest Editors' Foreword. 97
Costas Busch, Maurice Herlihy:
Sorting and Counting Networks of Arbitrary Width and Small Depth. 99-128
Bradley C. Kuszmaul, Dana S. Henry, Gabriel H. Loh:
A Comparison of Asymptotically Scalable Superscalar Processors. 129-150
Girija J. Narlikar:
Scheduling Threads for Low Space Requirement and Good Locality. 151-187
Rakesh D. Barve, Jeffrey Scott Vitter:
A Simple and Efficient Parallel Disk Mergesort. 189-215
Christof Krick, Friedhelm Meyer auf der Heide, Harald Räcke, Berthold Vöcking, Matthias Westermann:
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy. 217-245

Shang-Hua Teng:
Guest Editor's Foreward. 249
Susanne Albers:
On Generalized Connection Caching. 251-267
An-Chow Lai, Babak Falsafi:
Optimizing Traffic in DSM Clusters: Fine-Grain Memory Caching versus Page Migration/Replication. 269-287
Michael A. Bender, Michael O. Rabin:
Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk. 289-304
Robert Elsässer, Burkhard Monien, Robert Preis:
Diffusion Schemes for Load Balancing on Heterogeneous Networks. 305-320
Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe:
The Data Locality of Work Stealing. 321-347
Ole Agesen, David Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, Mark Moir, Nir Shavit, Guy L. Steele Jr.:
DCAS-Based Concurrent Deques. 349-386

Editorial Statement. 389
Phillip B. Gibbons, John L. Bruno, Steven Phillips:
Black-Box Correctness Tests for Basic Parallel Data Structures. 391-432
Olivier Bournez, Michael S. Branicky:
The Mortality Problem for Matrices of Low Dimensions. 433-448
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe:
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. 449-463
Takashi Yokomori:
Corrigendum Learning Two-Type Automata from Queries and Counterexamples. 465-466

Mitsunori Ogihara, Anne Condon:
Guest Editors' Foreword. 469
Andrei Paun:
P Systems with Global Rules. 471-481
Julia Khodor, David K. Gifford:
Programmed Mutagenesis Is Universal. 483-500
Andrzej Ehrenfeucht, Tero Harju, Ion Petre, Grzegorz Rozenberg:
Characterizing the Micronuclear Gene Patterns in Ciliates. 501-519
Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou:
Efficient On-Line Frequency Allocation and Call Control in Cellular Networks. 521-543
Shimon Even, Roni Kupershtok:
Laying Out the Interconnection Network of the Transpose Bijection. 545-558
Yingjie Liu:
The Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem. 559-564

Frank K. H. A. Dehne, Wolfgang Dittrich, David A. Hutchinson, Anil Maheshwari:
Bulk Synchronous Parallel Algorithms for the External Memory Model. 567-597
Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman, Walter Unger:
Scheduling Time-Constrained Communication in Linear Networks. 599-623
Grammati E. Pantziou, George P. Pentaris, Paul G. Spirakis:
Competitive Call Control in Mobile Networks. 625-639
Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana:
Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees. 641-665
Zvi Lotker, Boaz Patt-Shamir:
Average-Case Analysis of Greedy Packet Scheduling. 667-683