Automata, Languages and Programming: 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002. Proceedings: Lecture Notes in Computer Science, cartea 2380

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.

Includes supplementary material: sn.pub/extras