39. ICALP 2012: Warwick, UK - Part II
Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, Roger Wattenhofer (Eds.): Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II. Springer 2012 Lecture Notes in Computer Science ISBN 978-3-642-31584-8
Invited Talks
- Riccardo Colini-Baldeschi, Monika Henzinger, Stefano Leonardi, Martin Starnberger: On Multiple Keyword Sponsored Search Auctions with Budgets. 1-12
- Gilles Dowek: A Theory Independent Curry-De Bruijn-Howard Correspondence. 13-15
- David Harel: Standing on the Shoulders of a Giant - One Persons Experience of Turings Impact (Summary of the Alan M. Turing Lecture). 16-22
- Kohei Honda: Session Types and Distributed Computing. 23
- Daniel A. Spielman: Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations. 24-26
- Berthold Vöcking: Randomized Mechanisms for Multi-unit Auctions - (Extended Abstract). 27-29
Track B - Logic Semantics, Automata and Theory of Programming
- Luca Aceto, Arnaud Carayol, Zoltán Ésik, Anna Ingólfsdóttir: Algebraic Synchronization Trees and Processes. 30-41
- Albert Atserias, Anuj Dawar: Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. 67-78
- Mikolaj Bojanczyk, Slawomir Lasota: A Machine-Independent Characterization of Timed Languages. 92-103
- Mikolaj Bojanczyk, Thomas Place: Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets. 104-115
- Patricia Bouyer, Nicolas Markey, Ocan Sankur: Robust Reachability in Timed Automata: A Game-Based Approach. 128-140
- Tomás Brázdil, Antonín Kucera, Petr Novotný, Dominik Wojtczak: Minimizing Expected Termination Time in One-Counter Markov Decision Processes. 141-152
- Christopher H. Broadbent: Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata. 153-164
- Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, Olivier Serre: A Saturation Method for Collapsible Pushdown Systems. 165-176
- Volker Diekert, Manfred Kufleitner, Klaus Reinhardt, Tobias Walter: Regular Languages Are Church-Rosser Congruential. 177-188
- John Fearnley, Sven Schewe: Time and Parallelizability Results for Parity Games with Bounded Treewidth. 189-200
- Marcelo P. Fiore: Discrete Generalised Polynomial Functors - (Extended Abstract). 214-226
- Hongfei Fu: Computing Game Metrics on Markov Decision Processes. 227-238
- Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev: Exponential Lower Bounds and Separation for Query Rewriting. 263-274
- Manfred Kufleitner, Alexander Lauser: Lattices of Logical Fragments over Words - (Extended Abstract). 275-286
- Denis Kuperberg, Michael Vanden Boom: On the Expressive Power of Cost Logics over Infinite Words. 287-298
- C.-H. Luke Ong, Takeshi Tsukada: Two-Level Game Semantics, Intersection Types, and Recursion Schemes. 325-336
- Uday S. Reddy, Brian P. Dunphy: An Automata-Theoretic Model of Idealized Algol - (Extended Abstract). 337-350
- Grigore Rosu, Andrei Stefanescu: Towards a Unified Theory of Operational and Axiomatic Semantics. 351-363
- Sylvain Salvati, Giulio Manzonetto, Mai Gehrke, Henk Barendregt: Loader and Urzyczyn Are Logically Related. 364-376
- Szymon Torunczyk: Languages of Profinite Words and the Limitedness Problem. 377-389
- Yaron Velner: The Complexity of Mean-Payoff Automaton Expression. 390-402
Track C - Foundations of Networked Computation
- Leonid Barenboim: On the Locality of Some NP-Complete Problems. 403-415
- Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, Dror Rawitz: Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs. 416-427
- Andrew Berns, James Hegeman, Sriram V. Pemmaraju: Super-Fast Distributed Algorithms for Metric Facility Location. 428-439
- Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, Aneesh Sharma: Preventing Unraveling in Social Networks: The Anchored k-Core Problem. 440-451
- Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky: Edge Fault Tolerance on Sparse Networks. 452-463
- Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani: Computational Complexity of Traffic Hijacking under BGP and S-BGP. 476-487
- Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer: Efficiency-Revenue Trade-Offs in Auctions. 488-499
- Yoann Dieudonné, Andrzej Pelc: Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports. 500-512
- Khaled M. Elbassioni: A QPTAS for [InlineEquation not available: see fulltext.]-Envy-Free Profit-Maximizing Pricing on Line Graphs. 513-524
- Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michal Pilipczuk: Minimizing Rosenthal Potential in Multicast Games. 525-536
- Ran Gelles, Rafail Ostrovsky, Kina Winoto: Multiparty Proximity Testing with Dishonest Majority from Equality Testing. 537-548
- Michael T. Goodrich, Michael Mitzenmacher: Anonymous Card Shuffling and Its Applications to Parallel Mixnets. 549-560
- Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam, Vassilis Zikas: Byzantine Agreement with a Rational Adversary. 561-572
- Luca Gugelmann, Konstantinos Panagiotou, Ueli Peter: Random Hyperbolic Graphs: Degree Sequence and Clustering - (Extended Abstract). 573-585
- Navendu Jain, Ishai Menache, Joseph Naor, F. Bruce Shepherd: Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks. 586-597
- Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun: Counting Arbitrary Subgraphs in Data Streams. 598-609
- Adrian Kosowski, Bi Li, Nicolas Nisse, Karol Suchan: k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth. 610-622
- Marcel Ochel, Klaus Radke, Berthold Vöcking: Online Packing with Gradually Improving Capacity Estimations and Applications to Network Lifetime Maximization. 648-659
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team