Ebook: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II

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.

---

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.

---

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.
Content:
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 -

---

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.
Content:
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 -
....