Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II (Lecture Notes in Computer Science (7966))

This Two-volume Set Of Lncs 7965 And Lncs 7966 Constitutes The Refereed Proceedings Of The 40th International Colloquium On Automata, Languages And Programming, Icalp 2013, Held In Riga, Latvia, In July 2013. The Total Of 124 Revised Full Papers Presented Were Carefully Reviewed And Selected From 422 Submissions. They Are Organized In Three Tracks Focussing On Algorithms, Complexity And Games; Logic, Semantics, Automata And Theory Of Programming; And Foundations Of Networked Computation. Algorithms, Complexity And Games -- Logic, Semantics, Automata And Theory Of Programming -- Foundations Of Networked Computation. Edited By Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg. Front Matter....Pages - Algorithms, Networks, and Social Phenomena....Pages 1-3 Recent Advances for a Classical Scheduling Problem....Pages 4-14 Formalizing and Reasoning about Quality....Pages 15-27 The Square Root Phenomenon in Planar Graphs....Pages 28-28 A Guided Tour in Random Intersection Graphs....Pages 29-35 To Be Uncertain Is Uncomfortable, But to Be Certain Is Ridiculous....Pages 36-36 Decision Problems for Additive Regular Functions....Pages 37-48 Beyond Differential Privacy: Composition Theorems and Relational Logic for f -divergences between Probabilistic Programs....Pages 49-60 A Maximal Entropy Stochastic Process for a Timed Automaton,....Pages 61-73 Complexity of Two-Variable Logic on Finite Trees....Pages 74-88 Nondeterminism in the Presence of a Diverse or Unknown Future....Pages 89-100 Coalgebraic Announcement Logics....Pages 101-112 Self-shuffling Words....Pages 113-124 Block-Sorted Quantified Conjunctive Queries....Pages 125-136 From Security Protocols to Pushdown Automata....Pages 137-149 Efficient Separability of Regular Languages by Subsequences and Suffixes....Pages 150-161 On the Complexity of Verifying Regular Properties on Flat Counter Systems,....Pages 162-173 Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types....Pages 174-186 Component Reconfiguration in the Presence of Conflicts....Pages 187-198 Stochastic Context-Free Grammars, Regular Languages, and Newton’s Method....Pages 199-211 Reachability in Two-Clock Timed Automata Is PSPACE-Complete....Pages 212-223 Ramsey Goes Visibly Pushdown....Pages 224-237 Checking Equality and Regularity for Normed BPA with Silent Moves....Pages 238-249 FO Model Checking of Interval Graphs....Pages 250-262 Strategy Composition in Compositional Games....Pages 263-274 Asynchronous Games over Tree Architectures....Pages 275-286 Querying the Guarded Fragment with Transitivity....Pages 287-298 Contractive Signatures with Recursive Types, Type Parameters, and Abstract Types....Pages 299-311 Algebras, Automata and Logic for Languages of Labeled Birooted Trees....Pages 312-323 One-Variable Word Equations in Linear Time....Pages 324-335 The IO and OI Hierarchies Revisited....Pages 336-348 Evolving Graph-Structures and Their Implicit Computational Complexity....Pages 349-360 Rational Subsets and Submonoids of Wreath Products....Pages 361-372 Fair Subtyping for Open Session Types....Pages 373-384 Coeffects: Unified Static Analysis of Context-Dependence....Pages 385-397 Proof Systems for Retracts in Simply Typed Lambda Calculus....Pages 398-409 Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials....Pages 410-421 Revisiting the Equivalence Problem for Finite Multitape Automata....Pages 422-433 Silent Transitions in Automata with Storage....Pages 434-445 New Online Algorithms for Story Scheduling in Web Advertising....Pages 446-458 Sketching for Big Data Recommender Systems Using Fast Pseudo-random Fingerprints....Pages 459-471 Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds....Pages 472-483 On Revenue Maximization for Agents with Costly Information Acquisition....Pages 484-495 Price of Stability in Polynomial Congestion Games....Pages 496-507 Localization for a System of Colliding Robots....Pages 508-519 Fast Collaborative Graph Exploration....Pages 520-532 Deterministic Polynomial Approach in the Plane....Pages 533-544 Outsourced Pattern Matching....Pages 545-556 Learning a Ring Cheaply and Fast....Pages 557-568 Competitive Auctions for Markets with Positive Externalities....Pages 569-580 Efficient Computation of Balanced Structures....Pages 581-593 A Refined Complexity Analysis of Degree Anonymization in Graphs....Pages 594-606 Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks....Pages 607-619 Locally Stable Marriage with Strict Preferences....Pages 620-631 Distributed Deterministic Broadcasting in Wireless Networks of Weak Devices....Pages 632-644 Secure Equality and Greater-Than Tests with Sublinear Online Complexity....Pages 645-656 Temporal Network Optimization Subject to Connectivity Constraints....Pages 657-668 Strong Bounds for Evolution in Networks....Pages 669-680 Fast Distributed Coloring Algorithms for Triangle-Free Graphs....Pages 681-693 Back Matter....Pages -