18. STACS 2001:
Dresden,
Germany
Afonso Ferreira, Horst Reichel (Eds.):
STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings.
Lecture Notes in Computer Science 2010 Springer 2001, ISBN 3-540-41695-1 BibTeX
@proceedings{DBLP:conf/stacs/2001,
editor = {Afonso Ferreira and
Horst Reichel},
title = {STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer
Science, Dresden, Germany, February 15-17, 2001, Proceedings},
booktitle = {STACS},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {2010},
year = {2001},
isbn = {3-540-41695-1},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Invited Presentations
Contributions
- Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir:
2-Nested Simulation Is Not Finitely Equationally Axiomatizable.
39-50
Electronic Edition (Springer LINK) BibTeX
- Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe:
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
51-62
Electronic Edition (Springer LINK) BibTeX
- Helmut Alt, Christian Knauer, Carola Wenk:
Matching Polygonal Curves with Respect to the Fréchet Distance.
63-74
Electronic Edition (Springer LINK) BibTeX
- Andris Ambainis, Arnolds Kikusts, Maris Valdats:
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata.
75-86
Electronic Edition (Springer LINK) BibTeX
- Martin Beaudry, François Lemieux, Denis Thérien:
Star-Free Open Languages and Aperiodic Loops.
87-98
Electronic Edition (Springer LINK) BibTeX
- Markus Bläser:
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication.
99-109
Electronic Edition (Springer LINK) BibTeX
- Amit Chakrabarti, Subhash Khot, Yaoyun Shi:
Evasiveness of Subgraph Containment and Related Properties.
110-120
Electronic Edition (Springer LINK) BibTeX
- Andrea E. F. Clementi, Pierluigi Crescenzi, Paolo Penna, Gianluca Rossi, Paola Vocca:
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs.
121-131
Electronic Edition (Springer LINK) BibTeX
- Zhe Dang, Pierluigi San Pietro, Richard A. Kemmerer:
On Presburger Liveness of Discrete Timed Automata.
132-143
Electronic Edition (Springer LINK) BibTeX
- François Denis, Aurélien Lemay, Alain Terlutte:
Residual Finite State Automata.
144-157
Electronic Edition (Springer LINK) BibTeX
- Anders Dessmark, Andrzej Pelc:
Deterministic Radio Broadcasting at Low Cost.
158-169
Electronic Edition (Springer LINK) BibTeX
- Volker Diekert, Claudio Gutiérrez, Christian Hagenah:
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete.
170-182
Electronic Edition (Springer LINK) BibTeX
- Benjamin Doerr, Anand Srivastav:
Recursive Randomized Coloring Beats Fair Dice Random Colorings.
183-194
Electronic Edition (Springer LINK) BibTeX
- Rodney G. Downey, Denis R. Hirschfeldt, André Nies:
Randomness, Computability, and Density.
195-205
Electronic Edition (Springer LINK) BibTeX
- Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger:
On Multipartition Communication Complexity.
206-217
Electronic Edition (Springer LINK) BibTeX
- Robert Elsässer, Rastislav Kralovic, Burkhard Monien:
Scalable Sparse Topologies with Small Spectrum.
218-229
Electronic Edition (Springer LINK) BibTeX
- Leah Epstein:
Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios.
230-237
Electronic Edition (Springer LINK) BibTeX
- Cristina G. Fernandes, Till Nierhoff:
The UPS Problem.
238-246
Electronic Edition (Springer LINK) BibTeX
- Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer:
Gathering of Asynchronous Oblivious Robots with Limited Visibility.
247-258
Electronic Edition (Springer LINK) BibTeX
- Anahí Gajardo, Eric Goles Ch., Andrés Moreira:
Generalized Langton's Ant: Dynamical Behavior and Complexity.
259-270
Electronic Edition (Springer LINK) BibTeX
- Clemente Galdi, Christos Kaklamanis, Manuela Montangero, Pino Persiano:
Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals).
271-282
Electronic Edition (Springer LINK) BibTeX
- Ricard Gavaldà, Denis Thérien:
Learning Expressions over Monoids.
283-293
Electronic Edition (Springer LINK) BibTeX
- Andreas Goerdt, Michael Krivelevich:
Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods.
294-304
Electronic Edition (Springer LINK) BibTeX
- Massimiliano Goldwurm, Beatrice Palano, Massimo Santini:
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages.
305-316
Electronic Edition (Springer LINK) BibTeX
- Torben Hagerup, Torsten Tholey:
Efficient Minimal Perfect Hashing in Nearly Minimal Space.
317-326
Electronic Edition (Springer LINK) BibTeX
- Prahladh Harsha, Madhu Sudan:
Small PCPs with Low Query Complexity.
327-338
Electronic Edition (Springer LINK) BibTeX
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Series-Parallel Graphs.
339-352
Electronic Edition (Springer LINK) BibTeX
- David Janin, Jerzy Marcinkowski:
A Toolkit for First Order Extensions of Monadic Games.
353-364
Electronic Edition (Springer LINK) BibTeX
- Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs.
365-375
Electronic Edition (Springer LINK) BibTeX
- Matthias Jantzen, Alexy Kurganskyy:
Refining the Hierarchy of Blind Multicounter Languages.
376-387
Electronic Edition (Springer LINK) BibTeX
- Juhani Karhumäki, Leonid P. Lisovik:
A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab*c.
388-395
Electronic Edition (Springer LINK) BibTeX
- Jarkko Kari, Cristopher Moore:
New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata.
396-406
Electronic Edition (Springer LINK) BibTeX
- Lefteris M. Kirousis, Phokion G. Kolaitis:
The Complexity of Minimal Satisfiability Problems.
407-418
Electronic Edition (Springer LINK) BibTeX
- Matthias Krause, Stefan Lucks:
On the Minimal Hardware Complexity of Pseudorandom Function Generators.
419-430
Electronic Edition (Springer LINK) BibTeX
- Piotr Krysta, V. S. Anil Kumar:
Approximation Algorithms for Minimum Size 2-Connectivity Problems.
431-442
Electronic Edition (Springer LINK) BibTeX
- Dietrich Kuske:
A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets.
443-454
Electronic Edition (Springer LINK) BibTeX
- Clemens Lautemann, Nicole Schweikardt:
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases.
455-466
Electronic Edition (Springer LINK) BibTeX
- Giacomo Lenzi:
A New Logical Characterization of Büchi Automata.
467-477
Electronic Edition (Springer LINK) BibTeX
- Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph.
478-489
Electronic Edition (Springer LINK) BibTeX
- Markus Müller-Olm:
The Complexity of Copy Constant Detection in Parallel Programs.
490-501
Electronic Edition (Springer LINK) BibTeX
- Giri Narasimhan, Michiel H. M. Smid:
Approximation Algorithms for the Bottleneck Stretch Factor Problem.
502-513
Electronic Edition (Springer LINK) BibTeX
- Dirk Pattinson:
Semantical Principles in the Modal Logic of Coalgebras.
514-526
Electronic Edition (Springer LINK) BibTeX
- Klaus Reinhardt:
The #a = #b Pictures Are Recognizable.
527-538
Electronic Edition (Springer LINK) BibTeX
- Victor L. Selivanov:
A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages.
539-550
Electronic Edition (Springer LINK) BibTeX
- Howard Straubing, Denis Thérien:
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables.
551-562
Electronic Edition (Springer LINK) BibTeX
- Philipp Woelfel:
New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.
563-574
Electronic Edition (Springer LINK) BibTeX
Copyright © Sat May 16 23:43:06 2009
by Michael Ley (ley@uni-trier.de)