Skip to main content
SpringerLink
Log in

Automata, Languages and Programming

36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I

  • Conference proceedings
  • © 2009

Overview

Editors:
  1. Susanne Albers

    1. Department of Computer Science, University of Freiburg, Freiburg, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Alberto Marchetti-Spaccamela

    1. Department of Computer and Systems Sciences, Sapienza University of Rome, Roma, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Yossi Matias

    1. Google R&D Center, School of Computer Science, Tel Aviv University, Tel Aviv, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Sotiris Nikoletseas

    1. University of Patras and CTI, Patras, Greece

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Wolfgang Thomas

    1. RWTH Aachen, Lehrstuhl Informatik 7, Ahornstraße 55, Aachen, 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 5555)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: ICALP 2009.

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

  1. Front Matter

    Download chapter PDF

  2. Invited Lectures

    1. Assigning Papers to Referees

      • Kurt Mehlhorn
      Pages 1-2

    2. Algorithmic Game Theory: A Snapshot

      • Christos H. Papadimitriou
      Pages 3-11

  3. Contributed Papers

    1. SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs

      • Geir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja
      Pages 12-23

    2. Correlation Clustering Revisited: The “True” Cost of Error Minimization Problems

      • Nir Ailon, Edo Liberty
      Pages 24-36

    3. Sorting and Selection with Imprecise Comparisons

      • Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
      Pages 37-48

    4. Fast FAST

      • Noga Alon, Daniel Lokshtanov, Saket Saurabh
      Pages 49-58

    5. Bounds on the Size of Small Depth Circuits for Approximating Majority

      • Kazuyuki Amano
      Pages 59-70

    6. Counting Subgraphs via Homomorphisms

      • Omid Amini, Fedor V. Fomin, Saket Saurabh
      Pages 71-82

    7. External Sampling

      • Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
      Pages 83-94

    8. Functional Monitoring without Monotonicity

      • Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti
      Pages 95-106

    9. De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results

      • Yuriy Arbitman, Moni Naor, Gil Segev
      Pages 107-118

    10. Towards a Study of Low-Complexity Graphs

      • Sanjeev Arora, David Steurer, Avi Wigderson
      Pages 119-131

    11. Decidability of Conjugacy of Tree-Shifts of Finite Type

      • Nathalie Aubrun, Marie-Pierre Béal
      Pages 132-143

    12. Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule

      • Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz
      Pages 144-155

    13. Competitive Analysis of Aggregate Max in Windowed Streaming

      • Luca Becchetti, Elias Koutsoupias
      Pages 156-170

    14. Faster Regular Expression Matching

      • Philip Bille, Mikkel Thorup
      Pages 171-182

    15. A Fast and Simple Parallel Algorithm for the Monotone Duality Problem

      • Endre Boros, Kazuhisa Makino
      Pages 183-194

    16. Unconditional Lower Bounds against Advice

      • Harry Buhrman, Lance Fortnow, Rahul Santhanam
      Pages 195-209

    17. Approximating Decision Trees with Multiway Branches

      • Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal
      Pages 210-221
Back to top

Other volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Keywords

About this book

The two-volume set LNCS 5555 and LNCS 5556 constitutes the refereed proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, held in Rhodes, Greece, in July 2009.

The 126 revised full papers (62 papers for track A, 24 for track B, and 22 for track C) presented were carefully reviewed and selected from a total of 370 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games; on logic, semantics, theory of programming; as well as on foundations of networked computation: models, algorithms and information management.

LNCS 5555 contains 62 contributions of track A selected from 223 submissions as well as 2 invited lectures.

This two-volume set lauches the new subline of Lecture Notes in Computer Science, entitled LNCS Advanced Research in Computing and Software Science (ARCoSS).

Editors and Affiliations

  • Department of Computer Science, University of Freiburg, Freiburg, Germany

    Susanne Albers

  • Department of Computer and Systems Sciences, Sapienza University of Rome, Roma, Italy

    Alberto Marchetti-Spaccamela

  • Google R&D Center, School of Computer Science, Tel Aviv University, Tel Aviv, Israel

    Yossi Matias

  • University of Patras and CTI, Patras, Greece

    Sotiris Nikoletseas

  • RWTH Aachen, Lehrstuhl Informatik 7, Ahornstraße 55, Aachen, Germany

    Wolfgang Thomas

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation