Skip to main content
main-content

Über dieses Buch

ICALP 2009, the 36th edition of the International Colloquium on Automata, Languages and Programming, was held on the island of Rhodes, July 6–10, 2009. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS) which ?rst took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, complexity and games) and track B (focusing on logic, automata, semantics and theory of programming), and of the recently introduced track C (in 2009 focusing on foundations of networked computation). In response to the call for papers, the Program Committee received 370 s- missions: 223 for track A, 84 for track B and 63 for track C. Out of these, 108 papers were selected for inclusion in the scienti?c program: 62 papers for track A, 24 for track B and 22 for track C. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and many dese- ing papers could not be selected. ICALP 2009 consisted of ?ve invited lectures and the contributed papers.

Inhaltsverzeichnis

Frontmatter

Track B: Invited Lectures

2009 | OriginalPaper | Buchkapitel

A Survey of Stochastic Games with Limsup and Liminf Objectives

Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger

2009 | OriginalPaper | Buchkapitel

Tractable Optimization Problems through Hypergraph-Based Structural Restrictions

Georg Gottlob, Gianluigi Greco, Francesco Scarcello

Track B: Contributed Papers

2009 | OriginalPaper | Buchkapitel

Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types

Lucia Acciai, Michele Boreale

2009 | OriginalPaper | Buchkapitel

When Are Timed Automata Determinizable?

Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye

2009 | OriginalPaper | Buchkapitel

Faithful Loops for Aperiodic E-Ordered Monoids

(Extended Abstract)
Martin Beaudry, François Lemieux

2009 | OriginalPaper | Buchkapitel

Boundedness of Monadic Second-Order Formulae over Finite Words

Achim Blumensath, Martin Otto, Mark Weyer

2009 | OriginalPaper | Buchkapitel

Semilinear Program Feasibility

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

2009 | OriginalPaper | Buchkapitel

Floats and Ropes: A Case Study for Formal Numerical Program Verification

Sylvie Boldo

2009 | OriginalPaper | Buchkapitel

Reachability in Stochastic Timed Games

Patricia Bouyer, Vojtěch Forejt

2009 | OriginalPaper | Buchkapitel

Equations Defining the Polynomial Closure of a Lattice of Regular Languages

Mário J. J. Branco, Jean-Éric Pin

2009 | OriginalPaper | Buchkapitel

Approximating Markov Processes by Averaging

Philippe Chaput, Vincent Danos, Prakash Panangaden, Gordon Plotkin

2009 | OriginalPaper | Buchkapitel

The Theory of Stabilisation Monoids and Regular Cost Functions

Thomas Colcombet

2009 | OriginalPaper | Buchkapitel

A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

Thomas Colcombet, Konrad Zdanowski

2009 | OriginalPaper | Buchkapitel

On Constructor Rewrite Systems and the Lambda-Calculus

Ugo Dal Lago, Simone Martini

2009 | OriginalPaper | Buchkapitel

On Regular Temporal Logics with Past,

Christian Dax, Felix Klaedtke, Martin Lange

2009 | OriginalPaper | Buchkapitel

Forward Analysis for WSTS, Part II: Complete WSTS

Alain Finkel, Jean Goubault-Larrecq

2009 | OriginalPaper | Buchkapitel

Qualitative Concurrent Stochastic Games with Imperfect Information

Vincent Gripon, Olivier Serre

2009 | OriginalPaper | Buchkapitel

Diagrammatic Confluence and Completion

Jean-Pierre Jouannaud, Vincent van Oostrom

2009 | OriginalPaper | Buchkapitel

Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

Naoki Kobayashi, C. -H. Luke Ong

2009 | OriginalPaper | Buchkapitel

LTL Path Checking Is Efficiently Parallelizable

Lars Kuhtz, Bernd Finkbeiner

2009 | OriginalPaper | Buchkapitel

An Explicit Formula for the Free Exponential Modality of Linear Logic

Paul-André Melliès, Nicolas Tabareau, Christine Tasson

2009 | OriginalPaper | Buchkapitel

Decidability of the Guarded Fragment with the Transitive Closure

Jakub Michaliszyn

2009 | OriginalPaper | Buchkapitel

Weak Alternating Timed Automata

Pawel Parys, Igor Walukiewicz

2009 | OriginalPaper | Buchkapitel

A Decidable Characterization of Locally Testable Tree Languages

Thomas Place, Luc Segoufin

2009 | OriginalPaper | Buchkapitel

The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games

Michael Ummels, Dominik Wojtczak

Track C: Invited Lecture

2009 | OriginalPaper | Buchkapitel

Google’s Auction for TV Ads

Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal Varian, Dan Zigmond

Track C: Contributed Papers

2009 | OriginalPaper | Buchkapitel

Graph Sparsification in the Semi-streaming Model

Kook Jin Ahn, Sudipto Guha

2009 | OriginalPaper | Buchkapitel

Sort Me If You Can: How to Sort Dynamic Data

Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal

2009 | OriginalPaper | Buchkapitel

Maximum Bipartite Flow in Networks with Adaptive Channel Width

Yossi Azar, Aleksander Mądry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan

2009 | OriginalPaper | Buchkapitel

Mediated Population Protocols

Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis

2009 | OriginalPaper | Buchkapitel

Rumor Spreading in Social Networks

Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi

2009 | OriginalPaper | Buchkapitel

MANETS: High Mobility Can Make Up for Low Transmission Power

Andrea E. F. Clementi, Francesco Pasquale, Riccardo Silvestri

2009 | OriginalPaper | Buchkapitel

Multiple Random Walks and Interacting Particle Systems

Colin Cooper, Alan Frieze, Tomasz Radzik

2009 | OriginalPaper | Buchkapitel

Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies

Colin Cooper, David Ilcinkas, Ralf Klasing, Adrian Kosowski

2009 | OriginalPaper | Buchkapitel

On a Network Generalization of the Minmax Theorem

Constantinos Daskalakis, Christos H. Papadimitriou

2009 | OriginalPaper | Buchkapitel

Rate-Based Transition Systems for Stochastic Process Calculi

Rocco De Nicola, Diego Latella, Michele Loreti, Mieke Massink

2009 | OriginalPaper | Buchkapitel

Improved Algorithms for Latency Minimization in Wireless Networks

Alexander Fanghänel, Thomas Keßelheim, Berthold Vöcking

2009 | OriginalPaper | Buchkapitel

Efficient Methods for Selfish Network Design

Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis

2009 | OriginalPaper | Buchkapitel

Smoothed Analysis of Balancing Networks

Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik

2009 | OriginalPaper | Buchkapitel

Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures

Rachid Guerraoui, Eric Ruppert

2009 | OriginalPaper | Buchkapitel

Multi-armed Bandits with Metric Switching Costs

Sudipto Guha, Kamesh Munagala

2009 | OriginalPaper | Buchkapitel

Algorithms for Secretary Problems on Graphs and Hypergraphs

Nitish Korula, Martin Pál

2009 | OriginalPaper | Buchkapitel

Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps

Dariusz R. Kowalski, Andrzej Pelc

2009 | OriginalPaper | Buchkapitel

Secure Function Collection with Sublinear Storage

Maged H. Ibrahim, Aggelos Kiayias, Moti Yung, Hong-Sheng Zhou

2009 | OriginalPaper | Buchkapitel

Worst-Case Efficiency Analysis of Queueing Disciplines

Damon Mosk-Aoyama, Tim Roughgarden

2009 | OriginalPaper | Buchkapitel

On Observing Dynamic Prioritised Actions in SOC

Rosario Pugliese, Francesco Tiezzi, Nobuko Yoshida

2009 | OriginalPaper | Buchkapitel

A Distributed and Oblivious Heap

Christian Scheideler, Stefan Schmid

2009 | OriginalPaper | Buchkapitel

Proportional Response Dynamics in the Fisher Market

Li Zhang

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!

Bildnachweise