Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, Roger Wattenhofer
Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Part II
ICALP (2), 2012.

@proceedings{ICALP-v2-2012,
	address       = "Warwick, United Kingdom",
	doi           = "10.1007/978-3-642-31585-5",
	editor        = "Artur Czumaj and Kurt Mehlhorn and Andrew M. Pitts and Roger Wattenhofer",
	isbn          = "978-3-642-31584-8",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, Part II}",
	volume        = 7392,
	year          = 2012,
}

Contents (58 items)

8 ×#game studies
6 ×#network
5 ×#graph
4 ×#algorithm
4 ×#automaton
4 ×#multi
3 ×#algebra
3 ×#bound
3 ×#distributed
3 ×#logic

ICALP-v2-2012-BaldeschiHLS #keyword #multi #on the

On Multiple Keyword Sponsored Search Auctions with Budgets (RCB, MH, SL, MS), pp. 1–12.

ICALP-v2-2012-Dowek #independence

A Theory Independent Curry-De Bruijn-Howard Correspondence (GD), pp. 13–15.

ICALP-v2-2012-Harel #experience #summary

Standing on the Shoulders of a Giant — One Persons Experience of Turings Impact (Summary of the Alan M. Turing Lecture) (DH), pp. 16–22.

ICALP-v2-2012-Honda #distributed

Session Types and Distributed Computing (KH), p. 23.

ICALP-v2-2012-Spielman #algorithm #equation #graph #linear

Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations (DAS), pp. 24–26.

ICALP-v2-2012-Vocking #multi #random

Randomized Mechanisms for Multi-unit Auctions — (BV), pp. 27–29.

ICALP-v2-2012-AcetoCEI #algebra #process

Algebraic Synchronization Trees and Processes (LA, AC, ZÉ, AI), pp. 30–41.

ICALP-v2-2012-AlurD #streaming #transducer

Streaming Tree Transducers (RA, LD), pp. 42–53.

ICALP-v2-2012-ArrighiD #graph

Causal Graph Dynamics (PA, GD), pp. 54–66.

ICALP-v2-2012-AtseriasD #approximate #bound #quantifier

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers (AA, AD), pp. 67–78.

ICALP-v2-2012-BenediktBS #datalog #monad

Monadic Datalog Containment (MB, PB, PS), pp. 79–91.

ICALP-v2-2012-BojanczykL #independence

A Machine-Independent Characterization of Timed Languages (MB, SL), pp. 92–103.

ICALP-v2-2012-BojanczykP #infinity #regular expression #set

Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets (MB, TP), pp. 104–115.

ICALP-v2-2012-BojanczykP12a #towards

Toward Model Theory with Data Values (MB, TP), pp. 116–127.

ICALP-v2-2012-BouyerMS #approach #automaton #game studies #reachability #robust

Robust Reachability in Timed Automata: A Game-Based Approach (PB, NM, OS), pp. 128–140.

ICALP-v2-2012-BrazdilKNW #markov #process #termination

Minimizing Expected Termination Time in One-Counter Markov Decision Processes (TB, AK, PN, DW), pp. 141–152.

ICALP-v2-2012-Broadbent #automaton

Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata (CHB), pp. 153–164.

ICALP-v2-2012-BroadbentCHS #automaton

A Saturation Method for Collapsible Pushdown Systems (CHB, AC, MH, OS), pp. 165–176.

ICALP-v2-2012-DiekertKRW #regular expression

Regular Languages Are Church-Rosser Congruential (VD, MK, KR, TW), pp. 177–188.

ICALP-v2-2012-FearnleyS #bound #game studies

Time and Parallelizability Results for Parity Games with Bounded Treewidth (JF, SS), pp. 189–200.

ICALP-v2-2012-FernandezR #term rewriting

Nominal Completion for Rewrite Systems with Binders (MF, AR), pp. 201–213.

ICALP-v2-2012-Fiore #polynomial

Discrete Generalised Polynomial Functors — (MPF), pp. 214–226.

ICALP-v2-2012-Fu #game studies #markov #metric #process

Computing Game Metrics on Markov Decision Processes (HF), pp. 227–238.

ICALP-v2-2012-GavenciakKO #first-order

Deciding First Order Properties of Matroids (TG, DK, SiO), pp. 239–250.

ICALP-v2-2012-DawarH #algebra #game studies

Pebble Games with Algebraic Rules (AD, BH), pp. 251–262.

ICALP-v2-2012-KikotKPZ #bound #exponential #query

Exponential Lower Bounds and Separation for Query Rewriting (SK, RK, VVP, MZ), pp. 263–274.

ICALP-v2-2012-KufleitnerL #logic #word

Lattices of Logical Fragments over Words — (MK, AL), pp. 275–286.

ICALP-v2-2012-KuperbergB #infinity #logic #on the #power of #word

On the Expressive Power of Cost Logics over Infinite Words (DK, MVB), pp. 287–298.

ICALP-v2-2012-LitakPSS #algebra #logic

Coalgebraic Predicate Logic (TL, DP, KS, LS), pp. 299–311.

ICALP-v2-2012-MurawskiT #algorithm #game studies

Algorithmic Games for Full Ground References (ASM, NT), pp. 312–324.

ICALP-v2-2012-OngT #game studies #recursion #semantics

Two-Level Game Semantics, Intersection Types, and Recursion Schemes (CHLO, TT), pp. 325–336.

ICALP-v2-2012-ReddyD #algol #formal method

An Automata-Theoretic Model of Idealized Algol — (USR, BPD), pp. 337–350.

ICALP-v2-2012-RosuS #axiom #formal method #semantics #towards

Towards a Unified Theory of Operational and Axiomatic Semantics (GR, AS), pp. 351–363.

ICALP-v2-2012-SalvatiMGB

Loader and Urzyczyn Are Logically Related (SS, GM, MG, HB), pp. 364–376.

ICALP-v2-2012-Torunczyk #problem #word

Languages of Profinite Words and the Limitedness Problem (ST), pp. 377–389.

ICALP-v2-2012-Velner #automaton #complexity

The Complexity of Mean-Payoff Automaton Expression (YV), pp. 390–402.

ICALP-v2-2012-Barenboim #locality #on the #problem

On the Locality of Some NP-Complete Problems (LB), pp. 403–415.

ICALP-v2-2012-Bar-YehudaKKR #communication

Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs (RBY, EK, SK, DR), pp. 416–427.

ICALP-v2-2012-BernsHP #algorithm #distributed #metric

Super-Fast Distributed Algorithms for Metric Facility Location (AB, JH, SVP), pp. 428–439.

ICALP-v2-2012-BhawalkarKLRS #network #problem #social

Preventing Unraveling in Social Networks: The Anchored k-Core Problem (KB, JMK, KL, TR, AS), pp. 440–451.

ICALP-v2-2012-ChandranGO #fault tolerance #network

Edge Fault Tolerance on Sparse Networks (NC, JAG, RO), pp. 452–463.

ICALP-v2-2012-ChenDZZ

Incentive Ratios of Fisher Markets (NC, XD, HZ, JZ), pp. 464–475.

ICALP-v2-2012-ChiesaBEP #complexity

Computational Complexity of Traffic Hijacking under BGP and S-BGP (MC, GDB, TE, MP), pp. 476–487.

ICALP-v2-2012-DiakonikolasPPS #trade-off

Efficiency-Revenue Trade-Offs in Auctions (ID, CHP, GP, YS), pp. 488–499.

ICALP-v2-2012-DieudonneP #network

Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports (YD, AP), pp. 500–512.

ICALP-v2-2012-Elbassioni #graph

A QPTAS for ε-Envy-Free Profit-Maximizing Pricing on Line Graphs (KME), pp. 513–524.

ICALP-v2-2012-FominGNP #game studies #multi

Minimizing Rosenthal Potential in Multicast Games (FVF, PAG, JN, MP), pp. 525–536.

ICALP-v2-2012-GellesOW #multi #proximity #similarity #testing

Multiparty Proximity Testing with Dishonest Majority from Equality Testing (RG, RO, KW), pp. 537–548.

ICALP-v2-2012-GoodrichM #parallel

Anonymous Card Shuffling and Its Applications to Parallel Mixnets (MTG, MM), pp. 549–560.

ICALP-v2-2012-GroceKTZ

Byzantine Agreement with a Rational Adversary (AG, JK, AT, VZ), pp. 561–572.

ICALP-v2-2012-GugelmannPP #clustering #graph #random #sequence

Random Hyperbolic Graphs: Degree Sequence and Clustering — (LG, KP, UP), pp. 573–585.

ICALP-v2-2012-JainMNS #migration #network #virtual machine

Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks (NJ, IM, JN, FBS), pp. 586–597.

ICALP-v2-2012-KaneMSS #data type

Counting Arbitrary Subgraphs in Data Streams (DMK, KM, TS, HS), pp. 598–609.

ICALP-v2-2012-KosowskiLNS #graph

k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth (AK, BL, NN, KS), pp. 610–622.

ICALP-v2-2012-KoutsoupiasP #game studies

Contention Issues in Congestion Games (EK, KP), pp. 623–635.

ICALP-v2-2012-KrystaV #design #on the fly #online #random

Online Mechanism Design (Randomized Rounding on the Fly) (PK, BV), pp. 636–647.

ICALP-v2-2012-OchelRV #capacity #network #online

Online Packing with Gradually Improving Capacity Estimations and Applications to Network Lifetime Maximization (MO, KR, BV), pp. 648–659.

ICALP-v2-2012-PelegRT #algorithm #distributed #network

Distributed Algorithms for Network Diameter and Girth (DP, LR, ET), pp. 660–672.