Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Part II
ICALP (2), 2015.

@proceedings{ICALP-v2-2015,
	address       = "Kyoto, Japan",
	doi           = "10.1007/978-3-662-47666-6",
	editor        = "Magnús M. Halldórsson and Kazuo Iwama and Naoki Kobayashi and Bettina Speckmann",
	isbn          = "978-3-662-47665-9",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Part II}",
	volume        = 9135,
	year          = 2015,
}

Contents (56 items)

6 ×#game studies
5 ×#automaton
5 ×#network
5 ×#on the
4 ×#graph
4 ×#problem
3 ×#algebra
3 ×#approximate
3 ×#bound
3 ×#probability

ICALP-v2-2015-KawarabayashiK #graph #theorem #towards

Towards the Graph Minor Theorems for Directed Graphs (KiK, SK), pp. 3–10.

ICALP-v2-2015-Muscholl #automation #distributed #synthesis

Automated Synthesis of Distributed Controllers (AM), pp. 11–27.

ICALP-v2-2015-AbramskyJV #dependent type #game studies

Games for Dependent Types (SA, RJ, MV), pp. 31–43.

ICALP-v2-2015-AisenbergBBCI #principle #proving

Short Proofs of the Kneser-Lovász Coloring Principle (JA, MLB, SB, AC, GI), pp. 44–55.

ICALP-v2-2015-AmarilliBS

Provenance Circuits for Trees and Treelike Instances (AA, PB, PS), pp. 56–68.

ICALP-v2-2015-BenesBLS #automaton #parametricity

Language Emptiness of Continuous-Time Parametric Timed Automata (NB, PB, KGL, JS), pp. 69–81.

ICALP-v2-2015-Boreale #analysis #approximate #generative #probability

Analysis of Probabilistic Systems via Generating Functions and Padé Approximation (MB), pp. 82–94.

ICALP-v2-2015-BouajjaniEEH #on the #reachability

On Reducing Linearizability to State Reachability (AB, ME, CE, JH), pp. 95–107.

ICALP-v2-2015-Chatterjee0V #complexity #component #probability #synthesis

The Complexity of Synthesis from Probabilistic Components (KC, LD, MYV), pp. 108–120.

ICALP-v2-2015-ChatterjeeHIO #automaton #distance #edit distance

Edit Distance for Pushdown Automata (KC, TAH, RIJ, JO), pp. 121–133.

ICALP-v2-2015-CiobanuDE #equation #set

Solution Sets for Equations over Free Groups are EDT0L Languages (LC, VD, ME), pp. 134–145.

ICALP-v2-2015-ColcombetS #linear #order #quantifier #set

Limited Set quantifiers over Countable Linear Orderings (TC, AVS), pp. 146–158.

ICALP-v2-2015-DattaKMSZ #reachability

Reachability is in DynFO (SD, RK, AM, TS, TZ), pp. 159–170.

ICALP-v2-2015-DubutGG

Natural Homology (JD, EG, JGL), pp. 171–183.

ICALP-v2-2015-EtessamiSY #branch #equation #fixpoint #markov #polynomial #probability #process #reachability

Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes (KE, AS, MY), pp. 184–196.

ICALP-v2-2015-FijalkowHKS #bound #game studies #memory management

Trading Bounds for Memory in Games with Counters (NF, FH, DK, MS), pp. 197–208.

ICALP-v2-2015-FiliotMRT #problem #transducer

Decision Problems of Tree Transducers with Origin (EF, SM, PAR, JMT), pp. 209–221.

ICALP-v2-2015-Finkel #automaton #infinity #scalability #theorem #word

Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words (OF), pp. 222–233.

ICALP-v2-2015-HaaseK

The Odds of Staying on Budget (CH, SK), pp. 234–246.

ICALP-v2-2015-JagadeesanR #consistency #specification

From Sequential Specifications to Eventual Consistency (RJ, JR), pp. 247–259.

ICALP-v2-2015-JurdzinskiLS #energy #game studies #pseudo

Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time (MJ, RL, SS), pp. 260–272.

ICALP-v2-2015-KariS #algebra #approach #geometry

An Algebraic Geometric Approach to Nivat’s Conjecture (JK, MS), pp. 273–285.

ICALP-v2-2015-KozenMP0 #algebra

Nominal Kleene Coalgebra (DK, KM, DP, AS), pp. 286–298.

ICALP-v2-2015-KuperbergS #automaton #nondeterminism #on the

On Determinisation of Good-for-Games Automata (DK, MS), pp. 299–310.

ICALP-v2-2015-LahavV #memory management #modelling #reasoning

Owicki-Gries Reasoning for Weak Memory Models (OL, VV), pp. 311–323.

ICALP-v2-2015-LerouxST #automaton #on the #problem

On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension (JL, GS, PT), pp. 324–336.

ICALP-v2-2015-LohreyMP

Compressed Tree Canonization (ML, SM, FP), pp. 337–349.

ICALP-v2-2015-MazzaT

Parsimonious Types and Non-uniform Computation (DM, KT), pp. 350–361.

ICALP-v2-2015-MichalewskiM #higher-order #logic #monad #quantifier

Baire Category Quantifier in Monadic Second Order Logic (HM, MM), pp. 362–374.

ICALP-v2-2015-AminofRZS #liveness #network

Liveness of Parameterized Timed Networks (BA, SR, FZ, FS), pp. 375–387.

ICALP-v2-2015-ScheweTV #symmetry

Symmetric Strategy Improvement (SS, AT, TV), pp. 388–400.

ICALP-v2-2015-StatonU #algebra

Effect Algebras, Presheaves, Non-locality and Contextuality (SS, SU), pp. 401–413.

ICALP-v2-2015-SwernofskyW #complexity #on the

On the Complexity of Intersecting Regular, Context-Free, and Tree Languages (JS, MW), pp. 414–426.

ICALP-v2-2015-BojanczykMW #bound #clique #datalog #monad #source code

Containment of Monadic Datalog Programs via Bounded Clique-Width (MB, FM, AW), pp. 427–439.

ICALP-v2-2015-Zetzsche #approach

An Approach to Computing Downward Closures (GZ), pp. 440–451.

ICALP-v2-2015-Klein0 #game studies #how #infinity #lookahead #question

How Much Lookahead is Needed to Win Infinite Games? (FK, MZ), pp. 452–463.

ICALP-v2-2015-AchlioptasS #graph #independence #symmetry

Symmetric Graph Properties Have Independent Edges (DA, PS), pp. 467–478.

ICALP-v2-2015-AlistarhG #polynomial #protocol

Polylogarithmic-Time Leader Election in Population Protocols (DA, RG), pp. 479–491.

ICALP-v2-2015-AvinLNP #network

Core Size and Densification in Preferential Attachment Networks (CA, ZL, YN, DP), pp. 492–503.

ICALP-v2-2015-BhattacharyaHHK #maintenance

Maintaining Near-Popular Matchings (SB, MH, CCH, TK, LW), pp. 504–515.

ICALP-v2-2015-BringmannFHRS #network

Ultra-Fast Load Balancing on Scale-Free Networks (KB, TF, MH, RR, TS), pp. 516–527.

ICALP-v2-2015-Charron-BostFN #algorithm #approximate #network

Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms (BCB, MF, TN), pp. 528–539.

ICALP-v2-2015-ChattopadhyayR #communication

The Range of Topological Effects on Communication (AC, AR), pp. 540–551.

ICALP-v2-2015-ChenHKLM #information management

Secretary Markets with Local Information (NC, MH, MK, CL, PM), pp. 552–563.

ICALP-v2-2015-DahlgaardKR

A Simple and Optimal Ancestry Labeling Scheme for Trees (SD, MBTK, NR), pp. 564–574.

ICALP-v2-2015-DaniMSY #communication #interactive

Interactive Communication with Unknown Noise Rate (VD, MM, JS, MY), pp. 575–587.

ICALP-v2-2015-Feldmann #approximate #graph #parametricity #problem

Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs (AEF), pp. 588–600.

ICALP-v2-2015-FeldmanF #clustering #framework #game studies

A Unified Framework for Strong Price of Anarchy in Clustering Games (MF, OF), pp. 601–613.

ICALP-v2-2015-FriedrichK #graph #on the #random

On the Diameter of Hyperbolic Random Graphs (TF, AK), pp. 614–625.

ICALP-v2-2015-GairingKK #bound #game studies

Tight Bounds for Cost-Sharing in Weighted Congestion Games (MG, KK, GK), pp. 626–637.

ICALP-v2-2015-Ghaffari #distributed #towards

Distributed Broadcast Revisited: Towards Universal Optimality (MG), pp. 638–649.

ICALP-v2-2015-GiannakopoulosK

Selling Two Goods Optimally (YG, EK), pp. 650–662.

ICALP-v2-2015-GoldwasserKP #adaptation #revisited

Adaptively Secure Coin-Flipping, Revisited (SG, YTK, SP), pp. 663–674.

ICALP-v2-2015-KantorK #problem

Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem (EK, SK), pp. 675–687.

ICALP-v2-2015-KarbasiLS #network #normalisation

Normalization Phenomena in Asynchronous Networks (AK, JL, AS), pp. 688–700.

ICALP-v2-2015-Raykov

Broadcast from Minicast Secure Against General Adversaries (PR), pp. 701–712.