Automata, languages and programming(自动机、语言与程序设计)

This book constitutes the refereed proceedings of the 29th International Colloquium on Automata, Languages and Programming, ICALP 2002, held in Malaga, Spain, in July 2002.The 83 revised full papers presented together with 7 invited papers were carefully reviewed and selected from a total of 269 submissions. All current aspects of theoretical computer science are addressed and major new results are presented.

在线阅读本书

This book constitutes the refereed proceedings of the 29th International Colloquium on Automata, Languages and Programming, ICALP 2002, held in Malaga, Spain, in July 2002.The 83 revised full papers presented together with 7 invited papers were carefully reviewed and selected from a total of 269 submissions. All current aspects of theoretical computer science are addressed and major new results are presented.

Invited Talks
Molecular Assembly and Computation: From Theory to Experimentdl　Demonstrations
　Towards a Predictive Computational Complexity Theory
　Equivariant Syntax and Semantics
　L(A) = L(B)? Decidability Results from Complete Formal Systems
　Discrete Tomography: Reconstruction under Periodicity Constraints
　Local and Global Methods in Data Mining: Basic Techniques and　Open Problems
　Program Debugging and Validation Using Semantic Approximations　and Partial Specifications
Best Papers
　Inapproximability Results for Equations over Finite Groups
　A Faster All-Pairs Shortest Path Algorithm for Real-Weighted　Sparse Graphs
　On Families of Graphs Having a Decidable First Order Theory with　Reachability
Contributions
　Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws　in the Internet
　The Structure and Complexity of Nash Equilibria for a　Selfish Routing Game
　Control Message Aggregation in Group Communication Protocols
　Church-Rosser Languages vs. UCFL
　Intersection of Regular Languages and Star Hierarchy
　On the Construction of Reversible Automata for Reversible Languages
　Priority Queues, Pairing, and Adaptive Sorting
　Exponential Structures for Efficient Cache-Oblivious　Algorithms
　Bounded-Depth Frege Systems with Counting Axioms Polynomially　Simulate Nullstellensatz Refutations
　On the Complexity of Resolution with Bounded　Conjunctions
　Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes
　Perfect Constant-Round Secure Computation via Perfect Randomizing　Polynomials
　Exponential Lower Bound for Static Semi-algebraic Proofs
　Paths Problems in Symmetric Logarithmic Space
　Scheduling Search Procedures
　Removable Online Knapsack Problems
……
Author Index