This volume contains the contributions of the 29th International Colloquium on Automata, Languages, and Programming (ICALP) held July8 13, 2002 in M alaga, Spain. The diversityand the qualityof the scienti? c program of ICALP 2002 serve as evidence that theoretical computer science with all its aspects continues to be a vibrant ? eld and is increasinglyturning into a valuable and abundant source of ideas and concepts for other research disciplines and app- cations. ICALP has been the main annual scienti? c event of the European Assoc- tion for Theoretical Computer Science (EATCS) for almost thirtyyears, making ICALP one of the best-established conferences in theoretical computer science and EATCS one of the world s largest and oldest theoretical computer science organizations. To re? ect the two parts of the EATCS journal Theoretical Computer Science (TCS), ICALP s technical program is split into two parts: while track A is - voted to algorithms, automata, complexity, and games, track B focuses on logic, semantics, and theoryof programming.
Inhaltsverzeichnis
Invited Talks. - Molecular Assembly and Computation: From Theory to Experimental 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. - New Bounds for Variable-Sized and Resource Augmented Online Bin Packing. - TheQuest for Small Universal Cellular Automata. - Hyperbolic Recognition by Graph Automata. - Quantum and Stochastic Branching Programs of Bounded Width. - Spanning Trees with Bounded Number of Branch Vertices. - Energy Optimal Routing in Radio Networks Using Geometric Data Structures. - Gossiping with Bounded Size Messages in ad hoc Radio Networks. - The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences. - The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. - Constraint Satisfaction Problems in Non-deterministic Logarithmic Space. - Cache Oblivious Distribution Sweeping. - One-Probe Search. - New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. - Measuring the Probabilistic Powerdomain. - Games Characterizing Levy-Longo Trees. - Comparing Functional Paradigms for Exact Real-Number Computation. - Random Sampling from Boltzmann Principles. - On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures. - Bialgebraic Modelling of Timed Processes. - Testing Labelled Markov Processes. - Why Computational Complexity Requires Stricter Martingales. - Correspondence Principles for Effective Dimensions. - A Total Approach to Partial Algebraic Specification. - Axiomatising Divergence. - A Spatial Logic for Querying Graphs. - Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network. - Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. - Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths. - Synthesis of Uninitialized Systems. - Infinite-State High-Level MSCs: Model-Checking and Realizability. - Universal Inherence of Cycle-Free Context-Free Ambiguity Functions. - Histogramming Data Streams with Fast Per-Item Processing. - Finding Frequent Items in Data Streams. - Symbolic Strategy Synthesis for Games on Pushdown Graphs. - Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard. - Solving the String Statistics Problem in Time (nlogn). - A PTAS for Distinguishing (Sub)string Selection. - On the Theory of One-Step Rewriting in Trace Monoids. - Navigating with a Browser. - Improved Results for Stackelberg Scheduling Strategies. - Call Control in Rings. - Preemptive Scheduling in Overloaded Systems. - The Equivalence Problem of Finite Substitutions on ab*c, with Applications. - Deciding DPDA Equivalence Is Primitive Recursive. - Two-Way Alternating Automata and Finite Models. - Approximating Huffman Codes in Parallel. - Seamless Integration of Parallelism and Memory Hierarchy. - The Communication Complexity of Approximate Set Packing and Covering. - Antirandomizing the Wrong Game. - Fast Universalization of Investment Strategies with Provably Good Relative Returns. - Randomized Pursuit-Evasion in Graphs. - The Essence of Principal Typings. - Complete and Tractable Local Linear Time Temporal Logics over Traces. - An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces. - Random Numbers and an Incomplete Immune Recursive Set. - A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers. - Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem. - Finding a Path of Superlogarithmic Length. - Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs. - Improved Inapproximability Results for Vertex Cover on k-Uniform Hypergraphs. - Efficient Testing of Hypergraphs. - Optimal Net Surface Problems with Applications. - Wagner s Theorem on Realizers. - Circular Arrangements.