Luca Aceto, Monika Henzinger, Jirí Sgall
Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II
ICALP (2), 2011.

@proceedings{ICALP-v2-2011,
	address       = "Zurich, Switzerland",
	doi           = "10.1007/978-3-642-22012-8",
	editor        = "Luca Aceto and Monika Henzinger and Jirí Sgall",
	isbn          = "978-3-642-22011-1",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II}",
	volume        = 6756,
	year          = 2011,
}

Contents (52 items)

7 ×#automaton
6 ×#algorithm
5 ×#on the
4 ×#bound
4 ×#game studies
4 ×#probability
3 ×#convergence
3 ×#graph
3 ×#hybrid
3 ×#linear

ICALP-v2-2011-AlurD #nondeterminism #streaming #string #transducer

Nondeterministic Streaming String Transducers (RA, JVD), pp. 1–20.

ICALP-v2-2011-Shaltiel

An Introduction to Randomness Extractors (RS), pp. 21–41.

ICALP-v2-2011-Husfeldt #algorithm

Invitation to Algorithmic Uses of Inclusion-Exclusion (TH), pp. 42–59.

ICALP-v2-2011-AlvimACP #data flow #difference #on the #privacy

On the Relation between Differential Privacy and Quantitative Information Flow (MSA, MEA, KC, CP), pp. 60–76.

ICALP-v2-2011-Li #algorithm #approximate #problem

A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem (SL), pp. 77–88.

ICALP-v2-2011-Delacourt #automaton #set #theorem

Rice’s Theorem for μ-Limit Sets of Cellular Automata (MD), pp. 89–100.

ICALP-v2-2011-Chechik #fault tolerance #graph

Fault-Tolerant Compact Routing Schemes for General Graphs (SC), pp. 101–112.

ICALP-v2-2011-Hoefer #network #social

Local Matching Dynamics in Social Networks (MH), pp. 113–124.

ICALP-v2-2011-CartonCP #linear #order #regular expression #word

Regular Languages of Words over Countable Linear Orderings (OC, TC, GP), pp. 125–136.

ICALP-v2-2011-BeeckenMS #algebra #independence #testing

Algebraic Independence and Blackbox Identity Testing (MB, JM, NS), pp. 137–148.

ICALP-v2-2011-HopkinsMO #automaton #decidability #ml

A Fragment of ML Decidable by Visibly Pushdown Automata (DH, ASM, CHLO), pp. 149–161.

ICALP-v2-2011-SalvatiW #higher-order

Krivine Machines and Higher-Order Schemes (SS, IW), pp. 162–173.

ICALP-v2-2011-Katsumata

Relating Computational Effects by ⊤ ⊤-Lifting (SyK), pp. 174–185.

ICALP-v2-2011-LairdMM #category theory #difference #game studies

Constructing Differential Categories and Deconstructing Categories of Games (JL, GM, GM), pp. 186–197.

ICALP-v2-2011-Kapoutsis #nondeterminism

Nondeterminism Is Essential in Small 2FAs with Few Reversals (CAK), pp. 198–209.

ICALP-v2-2011-LohreyM #morphism #word

Isomorphism of Regular Trees and Words (ML, CM), pp. 210–221.

ICALP-v2-2011-Zetzsche #automaton #monad #on the #transducer

On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids (GZ), pp. 222–233.

ICALP-v2-2011-BenediktPR #cost analysis

The Cost of Traveling between Languages (MB, GP, CR), pp. 234–245.

ICALP-v2-2011-BertrandBBS #automaton #problem

Emptiness and Universality Problems in Timed Automata with Positive Frequency (NB, PB, TB, AS), pp. 246–257.

ICALP-v2-2011-Clemente #automaton

Büchi Automata Can Have Smaller Quotients (LC), pp. 258–270.

ICALP-v2-2011-ZhangJNH #model checking

Automata-Based CSL Model Checking (LZ, DNJ, FN, HH), pp. 271–282.

ICALP-v2-2011-ZhangB #model checking #probability

A Progress Measure for Explicit-State Probabilistic Model-Checkers (XZ, FvB), pp. 283–294.

ICALP-v2-2011-CrafaR #abstract interpretation #algorithm #bisimulation #probability #simulation

Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation (SC, FR), pp. 295–306.

ICALP-v2-2011-DengH #automaton #markov #on the #semantics

On the Semantics of Markov Automata (YD, MH), pp. 307–318.

ICALP-v2-2011-BrazdilKKV #analysis #bound #probability #recursion #runtime #source code

Runtime Analysis of Probabilistic Programs with Unbounded Recursion (TB, SK, AK, IHV), pp. 319–331.

ICALP-v2-2011-BrazdilBEK #approximate #game studies #probability #termination

Approximating the Termination Value of One-Counter MDPs and Stochastic Games (TB, VB, KE, AK), pp. 332–343.

ICALP-v2-2011-BovaCV #comparison

Generic Expression Hardness Results for Primitive Positive Formula Comparison (SB, HC, MV), pp. 344–355.

ICALP-v2-2011-BaranyCS

Guarded Negation (VB, BtC, LS), pp. 356–367.

ICALP-v2-2011-AndersonMSS #first-order #invariant #locality #logic #query

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates (MA, DvM, NS, LS), pp. 368–379.

ICALP-v2-2011-CardelliLM #composition #logic #markov

Modular Markovian Logic (LC, KGL, RM), pp. 380–391.

ICALP-v2-2011-SuenagaH #hybrid #modelling #programming

Programming with Infinitesimals: A While-Language for Hybrid System Modeling (KS, IH), pp. 392–403.

ICALP-v2-2011-FischerK #calculus #hybrid #linear #model checking #μ-calculus

Model Checking the Quantitative μ-Calculus on Linear Hybrid Systems (DF, LK), pp. 404–415.

ICALP-v2-2011-BrihayeDGORW #automaton #bound #hybrid #on the #reachability

On Reachability for Hybrid Automata over Bounded Time (TB, LD, GG, JO, JFR, JW), pp. 416–427.

ICALP-v2-2011-BouajjaniMM #robust

Deciding Robustness against Total Store Ordering (AB, RM, EM), pp. 428–440.

ICALP-v2-2011-SchmitzS #bound #multi #recursion

Multiply-Recursive Upper Bounds with Higman’s Lemma (SS, PS), pp. 441–452.

ICALP-v2-2011-GotsmanY #abstraction

Liveness-Preserving Atomicity Abstraction (AG, HY), pp. 453–465.

ICALP-v2-2011-KieferMOWZ #algorithm #on the

On Stabilization in Herman’s Algorithm (SK, ASM, JO, JW, LZ), pp. 466–477.

ICALP-v2-2011-MegowMS #algorithm #graph #online

Online Graph Exploration: New Results on Old and New Algorithms (NM, KM, PS), pp. 478–489.

ICALP-v2-2011-HermelinLWY #distance #graph

Distance Oracles for Vertex-Labeled Graphs (DH, AL, OW, RY), pp. 490–501.

ICALP-v2-2011-DoerrF #random

Asymptotically Optimal Randomized Rumor Spreading (BD, MF), pp. 502–513.

ICALP-v2-2011-ChanN #convergence #network #performance

Fast Convergence for Consensus in Dynamic Networks (THHC, LN), pp. 514–525.

ICALP-v2-2011-AhnG #linear #problem #programming

Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem (KJA, SG), pp. 526–538.

ICALP-v2-2011-KolliasR #game studies

Restoring Pure Equilibria to Weighted Congestion Games (KK, TR), pp. 539–551.

ICALP-v2-2011-CominettiCL

Existence and Uniqueness of Equilibria for Flows over Time (RC, JRC, OL), pp. 552–563.

ICALP-v2-2011-Huang #game studies

Collusion in Atomic Splittable Routing Games (CCH), pp. 564–575.

ICALP-v2-2011-GoodrichM #outsourcing #privacy #ram #simulation

Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation (MTG, MM), pp. 576–587.

ICALP-v2-2011-LibertY #adaptation

Adaptively Secure Non-interactive Threshold Cryptosystems (BL, MY), pp. 588–600.

ICALP-v2-2011-KarbasiIM

Content Search through Comparisons (AK, SI, LM), pp. 601–612.

ICALP-v2-2011-ChlebusKPR #ad hoc #communication #distributed #network #performance

Efficient Distributed Communication in Ad-Hoc Radio Networks (BSC, DRK, AP, MAR), pp. 613–624.

ICALP-v2-2011-HalldorssonM #bound #distributed #scheduling

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (MMH, PM), pp. 625–636.

ICALP-v2-2011-DamsHK #convergence

Convergence Time of Power-Control Dynamics (JD, MH, TK), pp. 637–649.

ICALP-v2-2011-Cord-LandwehrDFHKKKKMHRSWWW #algorithm #approach #convergence #mobile

A New Approach for Analyzing Convergence Algorithms for Mobile Robots (ACL, BD, MF, MH, BK, AK, PK, SK, MM, FMadH, CR, KS, DW, CW, DW), pp. 650–661.