Automata, Languages and Programming 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004, Proceedings
| Other Authors: | , , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2004, 2004
|
| Edition: | 1st ed. 2004 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- A -Approximation Algorithm for Rectangle Tiling
- Extensional Theories and Rewriting
- Hardness of String Similarity Search and Other Indexing Problems
- A Syntactic Characterization of Distributive LTL Queries
- Online Scheduling with Bounded Migration
- On the Expressive Power of Monadic Least Fixed Point Logic
- Counting in Trees for Free
- Games with Winning Conditions of High Borel Complexity
- Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas
- LA, Permutations, and the Hajós Calculus
- A Calibration ofIneffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles
- Efficiently Computing Succinct Trade-Off Curves
- On Randomization Versus Synchronization in Distributed Systems
- A New Algorithm for Optimal Constraint Satisfaction and Its Implications
- On the Power of Ambainis’s Lower Bounds
- Invited Talks
- Self-Adjusting Computation
- The Past, Present, and Future of Web Search Engines
- What Do Program Logics and Type Systems Have in Common?
- Feasible Proofs and Computations: Partnership and Fusion
- Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input
- Testing, Optimizaton, and Games
- Contributed Papers
- Deciding Knowledge in Security Protocols Under Equational Theories
- Representing Nested Inductive Types Using W-Types
- Algorithms for Multi-product Pricing
- Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas
- Linear and Branching Metrics for Quantitative Transition Systems
- Learning a Hidden Subgraph
- Optimal Reachability for Weighted Timed Games
- Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
- External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
- A ?-Calculus for Resource Separation
- A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems
- A Faster Algorithm for Minimum Cycle Basis of Graphs
- The Black-Box Complexity of Nearest Neighbor Search
- Regular Solutions of Language Inequalities and Well Quasi-orders
- A Calculus of Coroutines
- Almost Optimal Decentralized Routing in Long-Range Contact Networks
- Word Problems on Compressed Words
- Complexity of Pseudoknot Prediction in Simple Models
- Property Testing of Regular Tree Languages
- Entropy as a Fixed Point
- Transparent Long Proofs: A First PCP Theorem for
- A Time Lower Bound for Satisfiability
- Some Results on Effective Randomness
- A Polynomial Quantum Query Lower Bound for the Set Equality Problem
- Succinct Representations of Functions
- A Note on Karr’s Algorithm
- The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
- Efficient Consistency Proofs for Generalized Queries on a Committed Database
- Coloring Semirandom Graphs Optimally
- Sublinear-Time Approximation for Clustering Via Random Sampling
- Solving Two-Variable Word Equations
- Backtracking Games and Inflationary Fixed Points
- A PTAS for Embedding Hypergraph in a Cycle
- Towards an Algebraic Theory of Typed Mobile Processes
- Ecological Turing Machines
- Locally Consistent Constraint Satisfaction Problems
- Quantum Query Complexity of Some Graph Problems
- A Domain Theoretic Account of Picard’s Theorem
- Interactive Observability in Ludics
- Easily Refutable Subformulas of Large Random 3CNF Formulas
- On Graph Problems in a Semi-streaming Model
- Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks
- Bounded Fixed-Parameter Tractability and log2 n Nondeterministic Bits
- Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In
- Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up
- Selfish Unsplittable Flows
- The Power of Verification for One-Parameter Agents
- Group Spreading: A Protocol for Provably Secure Distributed Name Service
- Further Improvements in Competitive Guarantees for QoS Buffering
- Competition-Induced Preferential Attachment
- Approximating Longest Directed Paths and Cycles
- Definitions and Bounds for Self-Healing Key Distribution Schemes
- Tree-Walking Automata Cannot Be Determinized
- Projecting Games on Hypercoherences
- An Analog Characterization of Elementarily Computable Functions over the Real Numbers
- Model Checking with Multi-valued Logics
- The Complexity of Partition Functions
- Comparing Recursion, Replication, and Iteration in Process Calculi
- Dynamic Price Sequence and Incentive Compatibility
- The Complexity of Equivariant Unification
- Coordination Mechanisms
- Online Scheduling of Equal-Length Jobs:Randomization and Restarts Help
- Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
- A General Technique for Managing Strings in Comparison-Driven Data Structures
- Greedy Regular Expression Matching
- A Time Algorithm for d-Dimensional Protein Folding in the HP-Model
- Nash Equilibria in Discrete Routing Games with Convex Latency Functions
- Improved Results for Data Migration and Open Shop Scheduling
- Deterministic M2M Multicast in Radio Networks
- Syntactic Control of Concurrency
- Linear-Time List Decoding in Error-Free Settings
- A Categorical Model for the Geometry of Interaction
- Testing Monotonicity over Graph Products
- The Minimum-Entropy Set Cover Problem
- Communication Versus Computation
- Optimal Website Design with the Constrained Subtree Selection Problem.-Simple Permutations Mix Well
- Closest Pair Problems in Very High Dimensions
- Universality in Quantum Computation
- Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design
- Fairness to All While Downsizing