E-grāmata: Automata, Languages and Programming: 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002. Proceedings

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.- Wagners Theorem on Realizers.- Circular
Arrangements.