Skip to main content
SpringerLink
Log in

STACS 2000

17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Horst Reichel

    1. Faculty of Computer Science, Dept. of Theoretical Computer Science, Universität Dresden, Dresden, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Sophie Tison

    1. Université de Lille, LIFL - UPRESA 8022, CNRS, Bât. M3 - UFR IEEA, Villeneuve d’ASCQ Cedex, France

    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 1770)

Included in the following conference series:

Conference proceedings info: STACS 2000.

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 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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 (54 papers)

  1. Front Matter

    Pages I-XIV
    Download chapter PDF

  2. Codes and Graphs

    • M. Amin Shokrollahi
    Pages 1-12

  3. A Classification of Symbolic Transition Systems

    • Thomas A. Henzinger, Rupak Majumdar
    Pages 13-34

  4. Circuits versus Trees in Algebraic Complexity

    • Pascal Koiran
    Pages 35-52

  5. On the Many Faces of Block Codes

    • Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B. Sundar Rajan
    Pages 53-64

  6. A New Algorithm for MAX-2-SAT

    • Edward A. Hirsch
    Pages 65-73

  7. Bias Invariance of Small Upper Spans

    • Jack H. Lutz, Martin J. Strauss
    Pages 74-86

  8. The Complexity of Planarity Testing

    • Eric Allender, Meena Mahajan
    Pages 87-98

  9. About Cube-Free Morphisms

    • Gwénaël Richomme, Francis Wlazinski
    Pages 99-109

  10. Linear Cellular Automata with Multiple State Variables

    • Jarkko Kari
    Pages 110-121

  11. Two-Variable Word Equations

    • Lucian Ilie, Wojciech Plandowski
    Pages 122-132

  12. Average-Case Quantum Query Complexity

    • Andris Ambainis, Ronald de Wolf
    Pages 133-144

  13. Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs

    • Juraj Hromkovič, Martin Sauerhoff
    Pages 145-156

  14. The Boolean Hierarchy of NP-Partitions

    • Sven Kosub, Klaus W. Wagner
    Pages 157-168

  15. Binary Exponential Backoff Is Stable for High Arrival Rates

    • Hesham Al-Ammal, Leslie Ann Goldberg, Phil MacKenzie
    Pages 169-180

  16. The Data Broadcast Problem with Preemption

    • Nicolas Schabanel
    Pages 181-192

  17. An Approximate L p-Difference Algorithm for Massive Data Streams

    • Jessica H. Fong, Martin J. Strauss
    Pages 193-204

  18. Succinct Representations of Model Based Belief Revision

    • Paolo Penna
    Pages 205-216

  19. Logics Capturing Local Properties

    • Leonid Libkin
    Pages 217-229

  20. The Complexity of Poor Man’s Logic

    • Edith Hemaspaandra
    Pages 230-241
Back to top

Other volumes

  1. STACS 2000

Keywords

Editors and Affiliations

  • Faculty of Computer Science, Dept. of Theoretical Computer Science, Universität Dresden, Dresden, Germany

    Horst Reichel

  • Université de Lille, LIFL - UPRESA 8022, CNRS, Bât. M3 - UFR IEEA, Villeneuve d’ASCQ Cedex, France

    Sophie Tison

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation