Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings

Front Matter....Pages -
Self-Adjusting Computation....Pages 1-2
The Past, Present, and Future of Web Search Engines....Pages 3-3
What Do Program Logics and Type Systems Have in Common?....Pages 4-7
Feasible Proofs and Computations: Partnership and Fusion....Pages 8-14
Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input....Pages 15-27
Testing, Optimizaton, and Games....Pages 28-45
Deciding Knowledge in Security Protocols Under Equational Theories....Pages 46-58
Representing Nested Inductive Types Using W-Types....Pages 59-71
Algorithms for Multi-product Pricing....Pages 72-83
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas....Pages 84-96
Linear and Branching Metrics for Quantitative Transition Systems....Pages 97-109
Learning a Hidden Subgraph....Pages 110-121
Optimal Reachability for Weighted Timed Games....Pages 122-133
Wavelength Assignment in Optical Networks with Fixed Fiber Capacity....Pages 134-145
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs....Pages 146-157
A λ -Calculus for Resource Separation....Pages 158-170
The Power of Verification for One-Parameter Agents....Pages 171-182
Group Spreading: A Protocol for Provably Secure Distributed Name Service....Pages 183-195
Further Improvements in Competitive Guarantees for QoS Buffering....Pages 196-207
Competition-Induced Preferential Attachment....Pages 208-221
Approximating Longest Directed Paths and Cycles....Pages 222-233
Definitions and Bounds for Self-Healing Key Distribution Schemes....Pages 234-245
Tree-Walking Automata Cannot Be Determinized....Pages 246-256
Projecting Games on Hypercoherences....Pages 257-268
An Analog Characterization of Elementarily Computable Functions over the Real Numbers....Pages 269-280
Model Checking with Multi-valued Logics....Pages 281-293
The Complexity of Partition Functions....Pages 294-306
Comparing Recursion, Replication, and Iteration in Process Calculi....Pages 307-319
Dynamic Price Sequence and Incentive Compatibility....Pages 320-331
The Complexity of Equivariant Unification....Pages 332-344
Coordination Mechanisms....Pages 345-357
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help....Pages 358-370
Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities....Pages 371-382
Coloring Semirandom Graphs Optimally....Pages 383-395
Sublinear-Time Approximation for Clustering Via Random Sampling....Pages 396-407
Solving Two-Variable Word Equations....Pages 408-419
Backtracking Games and Inflationary Fixed Points....Pages 420-432
A PTAS for Embedding Hypergraph in a Cycle....Pages 433-444
Towards an Algebraic Theory of Typed Mobile Processes....Pages 445-456
Ecological Turing Machines....Pages 457-468
Locally Consistent Constraint Satisfaction Problems....Pages 469-480
Quantum Query Complexity of Some Graph Problems....Pages 481-493
A Domain Theoretic Account of Picard’s Theorem....Pages 494-505
Interactive Observability in Ludics....Pages 506-518
Easily Refutable Subformulas of Large Random 3CNF Formulas....Pages 519-530
On Graph Problems in a Semi-streaming Model....Pages 531-543
Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks....Pages 544-554
Bounded Fixed-Parameter Tractability and log 2 n Nondeterministic Bits....Pages 555-567
Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In....Pages 568-580
Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up....Pages 581-592
Selfish Unsplittable Flows....Pages 593-605
A General Technique for Managing Strings in Comparison-Driven Data Structures....Pages 606-617
Greedy Regular Expression Matching....Pages 618-629
A $2^{O(n^{1-{1\\over d}}\\log n)}$ Time Algorithm for d-Dimensional Protein Folding in the HP-Model....Pages 630-644
Nash Equilibria in Discrete Routing Games with Convex Latency Functions....Pages 645-657
Improved Results for Data Migration and Open Shop Scheduling....Pages 658-669
Deterministic M2M Multicast in Radio Networks....Pages 670-682
Syntactic Control of Concurrency....Pages 683-694
Linear-Time List Decoding in Error-Free Settings....Pages 695-707
A Categorical Model for the Geometry of Interaction....Pages 708-720
Testing Monotonicity over Graph Products....Pages 721-732
The Minimum-Entropy Set Cover Problem....Pages 733-744
Communication Versus Computation....Pages 745-756
Optimal Website Design with the Constrained Subtree Selection Problem....Pages 757-769
Simple Permutations Mix Well....Pages 770-781
Closest Pair Problems in Very High Dimensions....Pages 782-792
Universality in Quantum Computation....Pages 793-804
Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design....Pages 805-818
Fairness to All While Downsizing....Pages 819-830
A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems....Pages 831-845
A Faster Algorithm for Minimum Cycle Basis of Graphs....Pages 846-857
The Black-Box Complexity of Nearest Neighbor Search....Pages 858-869
Regular Solutions of Language Inequalities and Well Quasi-orders....Pages 870-881
A Calculus of Coroutines....Pages 882-893
Almost Optimal Decentralized Routing in Long-Range Contact Networks....Pages 894-905
Word Problems on Compressed Words....Pages 906-918
Complexity of Pseudoknot Prediction in Simple Models....Pages 919-931
Property Testing of Regular Tree Languages....Pages 932-944
Entropy as a Fixed Point....Pages 945-958
Transparent Long Proofs: A First PCP Theorem for $\\mbox{NP}_{\\mathbb R}$ ....Pages 959-970
A Time Lower Bound for Satisfiability....Pages 971-982
Some Results on Effective Randomness....Pages 983-995
A Polynomial Quantum Query Lower Bound for the Set Equality Problem....Pages 996-1005
Succinct Representations of Functions....Pages 1006-1015
A Note on Karr’s Algorithm....Pages 1016-1028
The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs....Pages 1029-1040
Efficient Consistency Proofs for Generalized Queries on a Committed Database....Pages 1041-1053
A $2 \\frac{1}{8}$ -Approximation Algorithm for Rectangle Tiling....Pages 1054-1065
Extensional Theories and Rewriting....Pages 1066-1079
Hardness of String Similarity Search and Other Indexing Problems....Pages 1080-1098
A Syntactic Characterization of Distributive LTL Queries....Pages 1099-1110
Online Scheduling with Bounded Migration....Pages 1111-1122
On the Expressive Power of Monadic Least Fixed Point Logic....Pages 1123-1135
Counting in Trees for Free....Pages 1136-1149
Games with Winning Conditions of High Borel Complexity....Pages 1150-1162
Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas....Pages 1163-1175
LA, Permutations, and the Hajós Calculus....Pages 1176-1187
A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles....Pages 1188-1200
Efficiently Computing Succinct Trade-Off Curves....Pages 1201-1213
On Randomization Versus Synchronization in Distributed Systems....Pages 1214-1226
A New Algorithm for Optimal Constraint Satisfaction and Its Implications....Pages 1227-1237
On the Power of Ambainis’s Lower Bounds....Pages 1238-1250
Back Matter....Pages -