附註:"EATCS"--Cover
Includes bibliographical references and index.
Invited Talks -- Self-Adjusting Computation -- The Past, Present, and Future of Web Search Engines -- What Do Program Logics and Type Systems Have in Common? -- Feasible Proofs and Computations: Partnership and Fusion -- Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input -- Testing, Optimizaton, and Games -- Contributed Papers -- Deciding Knowledge in Security Protocols Under Equational Theories -- Representing Nested Inductive Types Using W-Types -- Algorithms for Multi-product Pricing -- Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas -- Linear and Branching Metrics for Quantitative Transition Systems -- Learning a Hidden Subgraph -- Optimal Reachability for Weighted Timed Games -- Wavelength Assignment in Optical Networks with Fixed Fiber Capacity -- External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs -- A?-Calculus for Resource Separation -- The Power of Verification for One-Parameter Agents -- Group Spreading: A Protocol for Provably Secure Distributed Name Service -- Further Improvements in Competitive Guarantees for QoS Buffering -- Competition-Induced Preferential Attachment -- Approximating Longest Directed Paths and Cycles -- Definitions and Bounds for Self-Healing Key Distribution Schemes -- Tree-Walking Automata Cannot Be Determinized -- Projecting Games on Hypercoherences -- An Analog Characterization of Elementarily Computable Functions over the Real Numbers -- Model Checking with Multi-valued Logics -- The Complexity of Partition Functions -- Comparing Recursion, Replication, and Iteration in Process Calculi -- Dynamic Price Sequence and Incentive Compatibility -- The Complexity of Equivariant Unification -- Coordination Mechanisms -- Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help -- Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities -- Coloring Semirandom Graphs Optimally -- Sublinear-Time Appro
摘要:This book constitutes the refereed proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP 2004, held in Turku, Finland, in July 2004. The 97 revised full papers presented together with abstracts of 6 invited talks were carefully reviewed and selected from 379 submissions. The papers address all current issues in theoretical computer science including algorithms, automata, complexity, cryptography, database logics, program semantics, and programming theory.
