Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings

Polarized Process Algebra and Program Equivalence....Pages 1-21
Problems on RNA Secondary Structure Prediction and Design....Pages 22-32
Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks....Pages 33-33
The SPQR-Tree Data Structure in Graph Drawing....Pages 34-46
Model Checking and Testing Combined....Pages 47-63
Logic and Automata: A Match Made in Heaven....Pages 64-65
Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes....Pages 66-80
Generalized Framework for Selectors with Applications in Optimal Group Testing....Pages 81-96
Decoding of Interleaved Reed Solomon Codes over Noisy Data....Pages 97-108
On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces....Pages 109-118
Resource Access and Mobility Control with Dynamic Privileges Acquisition....Pages 119-132
Replication vs. Recursive Definitions in Channel Based Calculi....Pages 133-144
Improved Combinatorial Approximation Algorithms for the k -Level Facility Location Problem....Pages 145-156
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality....Pages 157-163
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities....Pages 164-175
Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem....Pages 176-188
Approximating Steiner k -Cuts....Pages 189-199
MAX k -CUT and Approximating the Chromatic Number of Random Graphs....Pages 200-211
Approximation Algorithm for Directed Telephone Multicast Problem....Pages 212-223
Mixin Modules and Computational Effects....Pages 224-238
Decision Problems for Language Equations with Boolean Operations....Pages 239-251
Generalized Rewrite Theories....Pages 252-266
Sophistication Revisited....Pages 267-277
Scaled Dimension and Nonuniform Complexity....Pages 278-290
Quantum Search on Bounded-Error Inputs....Pages 291-299
A Direct Sum Theorem in Communication Complexity via Message Compression....Pages 300-315
Optimal Cache-Oblivious Implicit Dictionaries....Pages 316-331
The Cell Probe Complexity of Succinct Data Structures....Pages 332-344
Succinct Representations of Permutations....Pages 345-356
Succinct Dynamic Dictionaries and Trees....Pages 357-368
Labeling Schemes for Weighted Dynamic Trees....Pages 369-383
A Simple Linear Time Algorithm for Computing a (2 k — 1)-Spanner of O ( n 1+1/k ) Size in Weighted Graphs....Pages 384-396
Multicommodity Flows over Time: Efficient Algorithms and Complexity....Pages 397-409
Multicommodity Demand Flow in a Tree....Pages 410-425
Skew and Infinitary Formal Power Series....Pages 426-438
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation....Pages 439-451
Residual Languages and Probabilistic Automata....Pages 452-463
A Testing Scenario for Probabilistic Automata....Pages 464-477
The Equivalence Problem for t -Turn DPDA Is Co-NP....Pages 478-489
Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k ....Pages 490-501
Convergence Time to Nash Equilibria....Pages 502-513
Nashification and the Coordination Ratio for a Selfish Routing Game....Pages 514-526
Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution....Pages 527-542
An Intersection Inequality for Discrete Distributions and Related Generation Problems....Pages 543-555
Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games....Pages 556-569
Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes....Pages 570-583
Bisimulation Proof Methods for Mobile Ambients....Pages 584-598
On Equivalent Representations of Infinite Structures....Pages 599-610
Adaptive Raising Strategies Optimizing Relative Efficiency....Pages 611-623
A Competitive Algorithm for the General 2-Server Problem....Pages 624-636
On the Competitive Ratio for Online Facility Location....Pages 637-652
A Study of Integrated Document and Connection Caching....Pages 653-667
A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems....Pages 668-680
Monadic Second-Order Logics with Cardinalities....Pages 681-696
 ∏ 2 ∩ Σ 2 ≡ AFMC ....Pages 697-713
Upper Bounds for a Theory of Queues....Pages 714-724
Degree Distribution of the FKP Network Model....Pages 725-738
Similarity Matrices for Pairs of Graphs....Pages 739-750
Algorithmic Aspects of Bandwidth Trading....Pages 751-766
CTL + Is Complete for Double Exponential Time....Pages 767-775
Hierarchical and Recursive State Machines with Context-Dependent Properties....Pages 776-789
Oracle Circuits for Branching-Time Model Checking....Pages 790-801
There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them)....Pages 802-816
The Computational Complexity of the Role Assignment Problem....Pages 817-828
Fixed-Parameter Algorithms for the ( k, r )-Center in Planar Graphs and Map Graphs....Pages 829-844
Genus Characterizes the Complexity of Graph Problems: Some Tight Results....Pages 845-856
The Definition of a Temporal Clock Operator....Pages 857-870
Minimal Classical Logic and Control Operators....Pages 871-885
Counterexample-Guided Control....Pages 886-902
Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types....Pages 903-917
Efficient Pebbling for List Traversal Synopses....Pages 918-928
Function Matching: Algorithms, Applications, and a Lower Bound....Pages 929-942
Simple Linear Work Suffix Array Construction....Pages 943-955
Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems....Pages 956-968
Secrecy in Untrusted Networks....Pages 969-983
Locally Commutative Categories....Pages 984-995
Semi-pullbacks and Bisimulations in Categories of Stochastic Relations....Pages 996-1007
Quantitative Analysis of Probabilistic Lossy Channel Systems....Pages 1008-1021
Discounting the Future in Systems Theory....Pages 1022-1037
Information Flow in Concurrent Games....Pages 1038-1053
Impact of Local Topological Information on Random Walks on Finite Graphs....Pages 1054-1067
Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces....Pages 1068-1079
Optimal Coding and Sampling of Triangulations....Pages 1080-1094
Generating Labeled Planar Graphs Uniformly at Random....Pages 1095-1107
Online Load Balancing Made Simple: Greedy Strikes Back....Pages 1108-1122
Real-Time Scheduling with a Budget....Pages 1123-1137
Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling....Pages 1138-1152
Anycasting in Adversarial Systems: Routing and Admission Control....Pages 1153-1168
Dynamic Algorithms for Approximating Interdistances....Pages 1169-1180
Solving the Robots Gathering Problem....Pages 1181-1196