Automata, Languages and Programming 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings /

Λεπτομέρειες βιβλιογραφικής εγγραφής
Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
Άλλοι συγγραφείς: Díaz, Josep (Επιμελητής έκδοσης), Karhumäki, Juhani (Επιμελητής έκδοσης), Lepistö, Arto (Επιμελητής έκδοσης), Sannella, Donald (Επιμελητής έκδοσης)
Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
Γλώσσα:English
Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2004.
Σειρά:Lecture Notes in Computer Science, 3142
Θέματα:
Διαθέσιμο Online:Full Text via HEAL-Link
Πίνακας περιεχομένων:
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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 of Ineffective 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.