Automata, Languages and Programming: 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings: Lecture Notes in Computer Science, cartea 2719

Invited Lectures.- Polarized Process Algebra and Program Equivalence.- Problems on RNA Secondary Structure Prediction and Design.- Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks.- The SPQR-Tree Data Structure in Graph Drawing.- Model Checking and Testing Combined.- Logic and Automata: A Match Made in Heaven.- Algorithms.- Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.- Generalized Framework for Selectors with Applications in Optimal Group Testing.- Decoding of Interleaved Reed Solomon Codes over Noisy Data.- Process Algebra.- On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces.- Resource Access and Mobility Control with Dynamic Privileges Acquisition.- Replication vs. Recursive Definitions in Channel Based Calculi.- Approximation Algorithms.- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem.- An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.- An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem.- Approximating Steiner k-Cuts.- MAX k-CUT and Approximating the Chromatic Number of Random Graphs.- Approximation Algorithm for Directed Telephone Multicast Problem.- Languages and Programming.- Mixin Modules and Computational Effects.- Decision Problems for Language Equations with Boolean Operations.- Generalized Rewrite Theories.- Complexity.- Sophistication Revisited.- Scaled Dimension and Nonuniform Complexity.- Quantum Search on Bounded-Error Inputs.- A Direct Sum Theorem in Communication Complexity via Message Compression.- Data Structures.- Optimal Cache-Oblivious Implicit Dictionaries.- TheCell Probe Complexity of Succinct Data Structures.- Succinct Representations of Permutations.- Succinct Dynamic Dictionaries and Trees.- Graph Algorithms.- Labeling Schemes for Weighted Dynamic Trees.- A Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs.- Multicommodity Flows over Time: Efficient Algorithms and Complexity.- Multicommodity Demand Flow in a Tree.- Automata.- Skew and Infinitary Formal Power Series.- Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation.- Residual Languages and Probabilistic Automata.- A Testing Scenario for Probabilistic Automata.- The Equivalence Problem for t-Turn DPDA Is Co-NP.- Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k.- Optimization and Games.- Convergence Time to Nash Equilibria.- Nashification and the Coordination Ratio for a Selfish Routing Game.- Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution.- An Intersection Inequality for Discrete Distributions and Related Generation Problems.- Graphs and Bisimulation.- Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games.- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes.- Bisimulation Proof Methods for Mobile Ambients.- On Equivalent Representations of Infinite Structures.- Online Problems.- Adaptive Raising Strategies Optimizing Relative Efficiency.- A Competitive Algorithm for the General 2-Server Problem.- On the Competitive Ratio for Online Facility Location.- A Study of Integrated Document and Connection Caching.- Verification.- A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems.- Monadic Second-Order Logics withCardinalities.- ? 2 ? ? 2 ? AFMC.- Upper Bounds for a Theory of Queues.- Around the Internet.- Degree Distribution of the FKP Network Model.- Similarity Matrices for Pairs of Graphs.- Algorithmic Aspects of Bandwidth Trading.- Temporal Logic and Model Checking.- CTL+ Is Complete for Double Exponential Time.- Hierarchical and Recursive State Machines with Context-Dependent Properties.- Oracle Circuits for Branching-Time Model Checking.- Graph Problems.- There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them).- The Computational Complexity of the Role Assignment Problem.- Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs.- Genus Characterizes the Complexity of Graph Problems: Some Tight Results.- Logic and Lambda-Calculus.- The Definition of a Temporal Clock Operator.- Minimal Classical Logic and Control Operators.- Counterexample-Guided Control.- Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types.- Data Structures and Algorithms.- Efficient Pebbling for List Traversal Synopses.- Function Matching: Algorithms, Applications, and a Lower Bound.- Simple Linear Work Suffix Array Construction.- Types and Categories.- Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems.- Secrecy in Untrusted Networks.- Locally Commutative Categories.- Probabilistic Systems.- Semi-pullbacks and Bisimulations in Categories of Stochastic Relations.- Quantitative Analysis of Probabilistic Lossy Channel Systems.- Discounting the Future in Systems Theory.- Information Flow in Concurrent Games.- Sampling and Randomness.- Impact of Local Topological Information on Random Walks on Finite Graphs.- Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces.- OptimalCoding and Sampling of Triangulations.- Generating Labeled Planar Graphs Uniformly at Random.- Scheduling.- Online Load Balancing Made Simple: Greedy Strikes Back.- Real-Time Scheduling with a Budget.- Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling.- Anycasting in Adversarial Systems: Routing and Admission Control.- Geometric Problems.- Dynamic Algorithms for Approximating Interdistances.- Solving the Robots Gathering Problem.