Automata, Languages and Programming 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings /
| Corporate Author: | |
|---|---|
| Other Authors: | , , , |
| Format: | Electronic eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2003.
|
| Edition: | 1st ed. 2003. |
| Series: | Lecture Notes in Computer Science,
2719 |
| Subjects: | |
| Online Access: | Full Text via HEAL-Link |
Table of Contents:
- Invited Lectures
- Polarized Process Algebra and Program Equivalence
- Problems on RNA Secondary Structure Prediction and Design
- Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks
- The SPQR-Tree Data Structure in Graph Drawing
- Model Checking and Testing Combined
- Logic and Automata: A Match Made in Heaven
- Algorithms
- Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes
- Generalized Framework for Selectors with Applications in Optimal Group Testing
- Decoding of Interleaved Reed Solomon Codes over Noisy Data
- Process Algebra
- On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces
- Resource Access and Mobility Control with Dynamic Privileges Acquisition
- Replication vs. Recursive Definitions in Channel Based Calculi
- Approximation Algorithms
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
- An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality
- An Improved Approximation Algorithm for Vertex Cover with Hard Capacities
- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem
- Approximating Steiner k-Cuts
- MAX k-CUT and Approximating the Chromatic Number of Random Graphs
- Approximation Algorithm for Directed Telephone Multicast Problem
- Languages and Programming
- Mixin Modules and Computational Effects
- Decision Problems for Language Equations with Boolean Operations
- Generalized Rewrite Theories
- Complexity
- Sophistication Revisited
- Scaled Dimension and Nonuniform Complexity
- Quantum Search on Bounded-Error Inputs
- A Direct Sum Theorem in Communication Complexity via Message Compression
- Data Structures
- Optimal Cache-Oblivious Implicit Dictionaries
- The Cell Probe Complexity of Succinct Data Structures
- Succinct Representations of Permutations
- Succinct Dynamic Dictionaries and Trees
- Graph Algorithms
- Labeling Schemes for Weighted Dynamic Trees
- A Simple Linear Time Algorithm for Computing a (2k - 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs
- Multicommodity Flows over Time: Efficient Algorithms and Complexity
- Multicommodity Demand Flow in a Tree
- Automata
- Skew and Infinitary Formal Power Series
- Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation
- Residual Languages and Probabilistic Automata
- A Testing Scenario for Probabilistic Automata
- The Equivalence Problem for t-Turn DPDA Is Co-NP
- Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k
- Optimization and Games
- Convergence Time to Nash Equilibria
- Nashification and the Coordination Ratio for a Selfish Routing Game
- Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution
- An Intersection Inequality for Discrete Distributions and Related Generation Problems
- Graphs and Bisimulation
- Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games
- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes
- Bisimulation Proof Methods for Mobile Ambients
- On Equivalent Representations of Infinite Structures
- Online Problems
- Adaptive Raising Strategies Optimizing Relative Efficiency
- A Competitive Algorithm for the General 2-Server Problem
- On the Competitive Ratio for Online Facility Location
- A Study of Integrated Document and Connection Caching
- Verification
- A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems
- Monadic Second-Order Logics with Cardinalities
- ? 2 ? ? 2 ? AFMC
- Upper Bounds for a Theory of Queues
- Around the Internet
- Degree Distribution of the FKP Network Model
- Similarity Matrices for Pairs of Graphs
- Algorithmic Aspects of Bandwidth Trading
- Temporal Logic and Model Checking
- CTL+ Is Complete for Double Exponential Time
- Hierarchical and Recursive State Machines with Context-Dependent Properties
- Oracle Circuits for Branching-Time Model Checking
- Graph Problems
- There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them)
- The Computational Complexity of the Role Assignment Problem
- Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs
- Genus Characterizes the Complexity of Graph Problems: Some Tight Results
- Logic and Lambda-Calculus
- The Definition of a Temporal Clock Operator
- Minimal Classical Logic and Control Operators
- Counterexample-Guided Control
- Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types
- Data Structures and Algorithms
- Efficient Pebbling for List Traversal Synopses
- Function Matching: Algorithms, Applications, and a Lower Bound
- Simple Linear Work Suffix Array Construction
- Types and Categories
- Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems
- Secrecy in Untrusted Networks
- Locally Commutative Categories
- Probabilistic Systems
- Semi-pullbacks and Bisimulations in Categories of Stochastic Relations
- Quantitative Analysis of Probabilistic Lossy Channel Systems
- Discounting the Future in Systems Theory
- Information Flow in Concurrent Games
- Sampling and Randomness
- Impact of Local Topological Information on Random Walks on Finite Graphs
- Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces
- Optimal Coding and Sampling of Triangulations
- Generating Labeled Planar Graphs Uniformly at Random
- Scheduling
- Online Load Balancing Made Simple: Greedy Strikes Back
- Real-Time Scheduling with a Budget
- Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling
- Anycasting in Adversarial Systems: Routing and Admission Control
- Geometric Problems
- Dynamic Algorithms for Approximating Interdistances
- Solving the Robots Gathering Problem.
