Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages and Programming

27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Ugo Montanari

    1. Department of Computer Sciences, University of Pisa, Pisa, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. José D. P. Rolim

    1. Center for Computer Sciences, University of Geneva, Geneva 4, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Emo Welzl

    1. Department of Computer Sciences, ETH Zurich, Zurich, Switzerland

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

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 (78 papers)

  1. Front Matter

    Pages I-XVI
    Download chapter PDF

  2. Invited Talk

    1. Game Semantics: Achievements and Prospects

      • Samson Abramsky
      Pages 1-1

    2. Clique Is Hard to Approximate within n 1-o(1)

      • Lars Engebretsen, Jonas Holmerin
      Pages 2-12

    3. Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time

      • Michael Krivelevich, H. Van Vu
      Pages 13-24

    4. Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming

      • Cristiano Calcagno, Eugenio Moggi, Walid Taha
      Pages 25-36

    5. A Statically Allocated Parallel Functional Language

      • Alan Mycroft, Richard Sharp
      Pages 37-48

    6. An Optimal Minimum Spanning Tree Algorithm

      • Seth Pettie, Vijaya Ramachandran
      Pages 49-60

    7. Improved Shortest Paths on the Word RAM

      • Torben Hagerup
      Pages 61-72

    8. Improved Algorithms for Finding Level Ancestors in Dynamic Trees

      • Stephen Alstrup, Jacob Holm
      Pages 73-84

    9. Lax Logical Relations

      • Gordon Plotkin, John Power, Donald Sannella, Robert Tennent
      Pages 85-102

    10. Reasoning about Idealized ALGOL Using Regular Languages

      • Dan R. Ghica, Guy McCusker
      Pages 103-115

    11. The Measurement Process in Domain Theory

      • Keye Martin
      Pages 116-126

  3. Invited Talk

    1. Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution

      • Gregor Engels, Reiko Heckel
      Pages 127-150

    2. Monotone Proofs of the Pigeon Hole Principle

      • Albert Atserias, Nicola Galesi, Ricard Gavaldá
      Pages 151-162

    3. Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models

      • Gerald Lüttgen, Michael Mendler
      Pages 163-174

    4. Algebraic Models for Contextual Nets

      • Roberto Bruni, Vladimiro Sassone
      Pages 175-186

    5. Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

      • Beate Bollig, Ingo Wegener
      Pages 187-198

    6. Measures of Nondeterminism in Finite Automata

      • Juraj Hromkovič, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
      Pages 199-210

    7. LTL Is Expressively Complete for Mazurkiewicz Traces

      • Volker Diekert, Paul Gastin
      Pages 211-223

    8. An Automata-Theoretic Completeness Proof for Interval Temporal Logic

      • Ben C. Moszkowski
      Pages 223-234
Back to top

Keywords

About this book

This book constitutes the refereed proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, held in Geneva, Switzerland in July 2000. The 69 revised full papers presented together with nine invited contributions were carefully reviewed and selected from a total of 196 extended abstracts submitted for the two tracks on algorithms, automata, complexity, and games and on logic, semantics, and programming theory. All in all, the volume presents an unique snapshot of the state-of-the-art in theoretical computer science.

Editors and Affiliations

  • Department of Computer Sciences, University of Pisa, Pisa, Italy

    Ugo Montanari

  • Center for Computer Sciences, University of Geneva, Geneva 4, Switzerland

    José D. P. Rolim

  • Department of Computer Sciences, ETH Zurich, Zurich, Switzerland

    Emo Welzl

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation