| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNISA996465893903316 |
|
|
Titolo |
Automata, Languages and Programming [[electronic resource] ] : 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings / / edited by Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 2003.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XXXVI, 1199 p.) |
|
|
|
|
|
|
Collana |
|
Lecture Notes in Computer Science, , 0302-9743 ; ; 2719 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Software engineering |
Computers |
Computer communication systems |
Data structures (Computer science) |
Computer science—Mathematics |
Software Engineering/Programming and Operating Systems |
Theory of Computation |
Computer Communication Networks |
Data Structures |
Mathematics of Computing |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references at the end of each chapters and index. |
|
|
|
|
|
|
|
|
Nota di contenuto |
|
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. |
|
|
|
|
|
| |