Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings (Lecture Notes in Computer Science, 2076, Band 2076) - Softcover

Softcover

ISBN 10: 3540422870 ISBN 13: 9783540422877

Verlag: Springer, 2001

Inhaltsangabe

Keynote Papers.- Algorithms, Games, and the Internet.- Automata, Circuits, and Hybrids: Facets of Continuous Time.- Invited Papers.- Languages, Rewriting Systems, and Verification of Infinite-State Systems.- Integrating Semantics for Object-Oriented System Models.- Modelling with Partial Orders - Why and Why Not?.- Theoretical Aspects of Evolutionary Algorithms.- Algebraic and Circuit Complexity.- Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical.- On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities.- Division Is In Uniform TC0.- Algorithm Analysis.- A Framework for Index Bulk Loading and Dynamization.- A Characterization of Temporal Locality and Its Portability across Memory Hierarchies.- The Complexity of Constructing Evolutionary Trees Using Experiments.- Hidden Pattern Statistics.- Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence.- All-Pairs Shortest Paths Computation in the BSP Model.- Approximation and Optimization.- Approximating the Minimum Spanning Tree Weight in Sublinear Time.- Approximation Hardness of TSP with Bounded Metrics.- The RPR 2 Rounding Technique for Semidefinite Programs.- Approximation Algorithms for Partial Covering Problems.- On the Online Bin Packing Problem.- Quick k-Median, k-Center, and Facility Location for Sparse Graphs.- Complexity.- Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems.- Subexponential Parameterized Algorithms Collapse the W-Hierarchy.- Improved Lower Bounds on the Randomized Complexity of Graph Properties.- New Imperfect Random Source with Applications to Coin-Flipping.- Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently.- Weisfeiler-Lehman Refinement Requires at Least a Linear Number ofIterations.- On Interactive Proofs with a Laconic Prover.- Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness.- Lower Bounds in the Quantum Cell Probe Model.- Concurrency.- Axiomatizations for Probabilistic Bisimulation.- Noninterference for Concurrent Programs.- Distributed Controller Synthesis for Local Specifications.- A Distributed Abstract Machine for Safe Ambients.- Towards Quantitative Verification of Probabilistic Transition Systems.- Efficient Datastructures.- Efficient Generation of Plane Triangulations without Repetitions.- The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations.- Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher.- A New Method for Balancing Binary Search Trees.- Graph Algorithms.- Permutation Editing and Matching via Embeddings.- Testing Hypergraph Coloring.- Total Colorings of Degenerated Graphs.- Decidable Properties of Graphs of All-Optical Networks.- Majority Consensus and the Local Majority Rule.- Language Theory, Codes, and Automata.- Solvability of Equations in Free Partially Commutative Groups Is decidable.- Rational Transformations of Formal Power Series.- Combinatorics of Three-Interval Exchanges.- Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages.- The Star Problem in Trace Monoids: Reductions Beyond C4.- The Trace Coding Problem Is Undecidable.- Combinatorics of Periods in Strings.- Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct.- Model Checking and Protocol Analysis.- Effective Lossy Queue Languages.- Model Checking of Unrestricted Hierarchical State Machines.- Symbolic Trace Analysis of Cryptographic Protocols.- Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols.- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata.- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width.- From Finite State Communication Protocols to High-Level Message Sequence Charts.- Networks and Routing.- Fractional Path Coloring with Applications to WDM Networks.- Performance Aspects of Distributed Caches Using TTL-Based Consistency.-

Details zur Ausgabe

• Verlag: Springer
• Erscheinungsdatum: 2001
• Sprache: Englisch
• ISBN 10: 3540422870
• ISBN 13: 9783540422877
• Einband: Taschenbuch
• Anzahl der Seiten: 1100
• Herausgeber: Orejas Fernando, Spirakis Paul G., Leeuwen Jan Van
• Kontakt zum Hersteller: ProductSafety@springernature.com; ProductSafety@springernature.com; ; Tiergartenstr. 17; Heidelberg; 69121; Deutschland