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

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.- Routing in Trees.- Online Packet Routing on Linear Arrays and Rings.- Faster Gossiping on Butterflies.- Reasoning and Verification.- Realizability and Verification of MSC Graphs.- Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs.- A Set-Theoretic Framework for Assume-Guarantee Reasoning.- Foundations for Circular Compositional Reasoning.- Scheduling.- A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.- The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.- On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates.- On the Approximability of Average Completion Time Scheduling under Precedence Constraints.- Secure Computation.- Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds.- Information-Theoretic Private Information Retrieval: A Unified Construction.- Secure Multiparty Computation of Approximations.- Secure Games with Polynomial Expressions.- Specification and Deduction.- On the Completeness of Arbitrary Selection Strategies for Paramodulation.- An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS.- Knuth-Bendix Constraint Solving Is NP-Complete.- Amalgamation in CASL via Enriched Signatures.- Structural Complexity.- Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution.- Time and Space Bounds forReversible Simulation.- Finite-State Dimension.- The Complexity of Computing the Size of an Interval.- Communication Gap for Finite Memory Devices.- Separating Quantum and Classical Learning.

Includes supplementary material: sn.pub/extras