Skip to main content
SpringerLink
Log in
Book cover

STACS 2001

18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings

  • Conference proceedings
  • © 2001

Overview

Editors:
  1. Afonso Ferreira

    1. I3S & INRIA Sophia Antipolis INRIA, CNRS, Sophia-Antipolis, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Horst Reichel

    1. Institut für Theoretische Informatik, Fakultät Informatik, TU Dresden, Dresden, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2010)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (49 papers)

  1. Front Matter

    Pages I-XV
    Download chapter PDF

  3. Contributions

    1. 2-Nested Simulation Is Not Finitely Equationally Axiomatizable

      • Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir
      Pages 39-50

    2. On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

      • Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
      Pages 51-62

    3. Matching Polygonal Curves with Respect to the Fréchet Distance

      • Helmut Alt, Christian Knauer, Carola Wenk
      Pages 63-74

    4. On the Class of Languages Recognizable by 1-Way Quantum Finite Automata

      • Andris Ambainis1, Arnolds KĶikusts, Māris Valdats
      Pages 75-86

    5. Star-Free Open Languages and Aperiodic Loops

      • Martin Beaudry, François Lemieux, Denis Thérien3
      Pages 87-98

    6. A 5/2n 2-Lower Bound for the Multiplicative Complexity of n × n-Matrix Multiplication

      • Markus Bläser
      Pages 99-109

    7. Evasiveness of Subgraph Containment and Related Properties

      • Amit Chakrabarti, Subhash Khot, Yaoyun Shi
      Pages 110-120

    8. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs

      • Andrea E. F. Clementi, Pilu Crescenzi, Paolo Penna, Gianluca Rossi, Paola Vocca
      Pages 121-131

    9. On Presburger Liveness of Discrete Timed Automata

      • Zhe Dang, Pierluigi San Pietro, Richard A. Kemmerer
      Pages 132-143

    10. Residual Finite State Automata

      • François Denis, Aurélien Lemay, Alain Terlutte
      Pages 144-157

    11. Deterministic Radio Broadcasting at Low Cost

      • Anders Dessmark, Andrzej Pelc
      Pages 158-169

    12. The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete

      • Volker Diekert, Claudio Gutiérrez, Christian Hagenah
      Pages 170-182

    13. Recursive Randomized Coloring Beats Fair Dice Random Colorings

      • Benjamin Doerr, Anand Srivastav
      Pages 183-194

    14. Randomness, Computability, and Density

      • Rod G. Downey, Denis R. Hirschfeldt, André Nies
      Pages 195-205

    15. On Multipartition Communication Complexity

      • Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
      Pages 206-217

    16. Scalable Sparse Topologies with Small Spectrum

      • Robert Elsässer, Rastislav Královič, Burkhard Monien
      Pages 218-229
Back to top

Keywords

Editors and Affiliations

  • I3S & INRIA Sophia Antipolis INRIA, CNRS, Sophia-Antipolis, France

    Afonso Ferreira

  • Institut für Theoretische Informatik, Fakultät Informatik, TU Dresden, Dresden, Germany

    Horst Reichel

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation