Theory of Computing Systems, Volume 36

Volume 36, Number 1, January 2003

Patrizio Cintioli, Riccardo Silvestri:
Polynomial Time Introreducibility. 1-15
Debashis Bera, Madhumangal Pal, Tapan Kumar Pal:
An Efficient Algorithm for Finding All Hinge Vertices on Trapezoid Graphs. 17-27
Howard Straubing, Denis Thérien:
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. 29-69
Satyanarayana V. Lokam:
Graph Complexity and Slice Functions. 71-88
Juha Honkala:
The Equivalence Problem of Polynomially Bounded D0L Systems - a Bound Depending Only on the Size of the Alphabet. 89-103

Jin-yi Cai:
Essentially Every Unimodular Matrix Defines an Expander. 105-135
Paola Flocchini, Flaminia L. Luccio:
Routing in Series Parallel Networks. 137-157
Juraj Hromkovic, Martin Sauerhoff:
The Power of Nondeterminism and Randomness for Oblivious Branching Programs. 159-182
Symeon Bozapalidis:
Extending Stochastic and Quantum Functions. 183-197
Stephen A. Fenner:
PP-Lowness and a Simple Definition of AWPP. 199-212

Fabrice Noilhan, Miklos Santha:
Semantical Counting Circuits. 217-229
Vincent D. Blondel, Vincent Canterini:
Undecidable Problems for Probabilistic Automata of Fixed Dimension. 231-245
Zoltán Fülöp, Heiko Vogler:
Tree Series Transformations that Respect Copying. 247-293
Richard J. Lipton, Mitsunori Ogihara, Yechezkel Zalcstein:
A Note on Square Rooting of Time Functions of Turing Machines. 295-299

Eric Allender, Vikraman Arvind, Meena Mahajan:
Arithmetic Complexity, Kleene Closure, and Formal Power Series. 303-328
Yossi Matias, Jeffrey Scott Vitter, Wen-Chun Ni:
Dynamic Generation of Discrete Random Variates. 329-358
Alina Beygelzimer, Mitsunori Ogihara:
The (Non)Enumerability of the Determinant and the Rank. 359-374
Jörg Rothe, Holger Spakowski, Jörg Vogel:
Exact Complexity of the Winner Problem for Young Elections. 375-386
Vince Grolmusz, Gábor Tardos:
A Note on Non-Deterministic Communication Complexity with Few Witnesses. 387-391

Guy E. Blelloch, Perry Cheng, Phillip B. Gibbons:
Scalable Room Synchronizations. 397-430
Anne Condon, Alan J. Hu:
Automatable Verification of Sequential Consistency. 431-460
Robert Elsässer, Thomas Lücking, Burkhard Monien:
On Spectral Bounds for the k-Partitioning of Graphs. 461-478
Shay Kutten, David Peleg, Uzi Vishkin:
Deterministic Resource Discovery in Distributed Networks. 479-495
Christof Krick, Harald Räcke, Matthias Westermann:
Approximation Algorithms for Data Management in Networks. 497-519
Dorit Naishlos, Joseph Nuzman, Chau-Wen Tseng, Uzi Vishkin:
Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach. 521-552
Sotiris E. Nikoletseas, Grigorios Prasinos, Paul G. Spirakis, Christos D. Zaroliagis:
Attack Propagation in Networks. 553-574
Francisca Quintana, Jesús Corbal, Roger Espasa, Mateo Valero:
A Cost-Effective Architecture for Vectorizable Numerical and Multimedia Applications. 575-593

Hiro Ito, Kazuo Iwama, Yasuo Okabe, Takuya Yoshihiro:
Avoiding Routing Loops on the Internet. 597-609
Konrad Schlude, Eljas Soisalon-Soininen, Peter Widmayer:
Distributed Search Trees: Fault Tolerance in an Asynchronous Environment. 611-629
Emmanuel Godard, Yves Métivier:
Deducible and Equivalent Structural Knowledges in Distributed Algorithms. 631-654
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin:
Asymmetric Communication Protocols via Hotlink Assignments. 655-661
Jean-Claude Bermond, Sébastien Choplin, Stephane Perennes:
Hierarchical Ring Network design. 663-682
Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis:
Approximate Equilibria and Ball Fusion. 683-693
Stefan Dobrev:
Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults. 695-709
Bogdan S. Chlebus, Karol Golab, Dariusz R. Kowalski:
Broadcasting Spanning Forests on a Multiple-Access Channel. 711-733

Last update Sat May 26 06:51:22 2012 CET by the DBLP Team —

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