@incollection{Colini-Baldeschi-Henzinger-Leonardi-Starnberger/12,
AUTHOR = {Colini-Baldeschi, Riccardo and Henzinger, Monika and Leonardi, Stefano and Starnberger, Martin},
TITLE = {On-multiple keyword sponsored search auctions with budgets},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {1-12},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dowek/12,
AUTHOR = {Dowek, Gilles},
TITLE = {A theory independent Curry-De Bruijn-Howard correspondence},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {13-15},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Harel/12,
AUTHOR = {Harel, David},
TITLE = {Standing on the shoulders of a giant: One persons experience of Turings impact},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {16-22},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Honda/12,
AUTHOR = {Honda, Kohei},
TITLE = {Session types and distributed computing},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {23-23},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Spielman/12,
AUTHOR = {Spielman, Daniel A.},
TITLE = {Algorithms, graph theory, and the solution of Laplacian linear equations},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {24-26},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Vocking/12,
AUTHOR = {V{\"o}cking, Berthold},
TITLE = {Randomized mechanisms for multi-unit auctions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {27-29},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {Extended abstract},
}
@incollection{Aceto-Carayol-Esik-Ingolfsdottir/12,
AUTHOR = {Aceto, Luca and Carayol, Arnaud and {\'E}sik, Zolt{\'a}n and Ing{\'o}lfsd{\'o}ttir, Anna},
TITLE = {Algebraic synchronization trees and processes},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {30-41},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alur-DAntoni/12,
AUTHOR = {Alur, Rajeev and D'Antoni, Loris},
TITLE = {Streaming tree transducers},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {42-53},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arrighi-Dowek/12a,
AUTHOR = {Arrighi, Pablo and Dowek, Gilles},
TITLE = {Causal graph dynamics},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {54-66},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Atserias-Dawar/12,
AUTHOR = {Atserias, Albert and Dawar, Anuj},
TITLE = {Degree lower bounds of tower-type for approximating formulas with parity quantifiers},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {67-78},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Benedikt-Bourhis-Senellart/12,
AUTHOR = {Benedikt, Michael and Bourhis, Pierre and Senellart, Pierre},
TITLE = {Monadic datalog containment},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {79-91},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bojanczyk-Lasota/12,
AUTHOR = {Boja{\'n}czyk, Miko{\l}aj and Lasota, S{\l}awomir},
TITLE = {A machine-independent characterization of timed languages},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {92-103},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bojanczyk-Place/12,
AUTHOR = {Boja{\'n}czyk, Miko{\l}aj and Place, Thomas},
TITLE = {Regular languages of infinite trees that are Boolean combinations of open sets},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {104-115},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bojanczyk-Place/12a,
AUTHOR = {Boja{\'n}czyk, Miko{\l}aj and Place, Thomas},
TITLE = {Toward model theory with data values},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {116-127},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bouyer-Markey-Sankur/12,
AUTHOR = {Bouyer, Patricia and Markey, Nicolas and Sankur, Ocan},
TITLE = {Robust reachability in timed automata: A game-based approach},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {128-140},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brazdil-Kucera-Novotny-Wojtczak/12,
AUTHOR = {Br{\'a}zdil, Tom{\'a}{\v{s}} and Ku{\v{c}}era, Anton{\'{i}}n and Novotn{\'y}, Petr and Wojtczak, Dominik},
TITLE = {Minimizing expected termination time in one-counter Markov decision processes},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {141-152},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Broadbent/12,
AUTHOR = {Broadbent, Christopher},
TITLE = {Prefix rewriting for nested-words and collapsible pushdown automata},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {153-164},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Broadbent-Carayol-Hague-Serre/12,
AUTHOR = {Broadbent, Chris and Carayol, Arnaud and Hague, Matthew and Serre, Olivier},
TITLE = {A saturation method for collapsible pushdown systems},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {165-176},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Diekert-Kufleitner-Reinhardt-Walter/12,
AUTHOR = {Diekert, Volker and Kufleitner, Manfred and Reinhardt, Klaus and Walter, Tobias},
TITLE = {Regular languages are Church-Rosser congruential},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {177-188},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fearnley-Schewe/12,
AUTHOR = {Fearnley, John and Schewe, Sven},
TITLE = {Time and parallelizability results for parity games with bounded treewidth},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {189-200},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fernandez-Rubio/12,
AUTHOR = {Fern{\'a}ndez, Maribel and Rubio, Albert},
TITLE = {Nominal completion for rewrite systems with binders},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {201-213},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiore/12,
AUTHOR = {Fiore, Marcelo},
TITLE = {Discrete generalised polynomial functors},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {214-226},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {Extended abstract},
}
@incollection{Fu/12,
AUTHOR = {Fu, Hongfei},
TITLE = {Computing game metrics on Markov decision processes},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {227-238},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gavenciak-Kral-Oum/12,
AUTHOR = {Gaven{\v{c}}iak, Tom{\'a}{\v{s}} and Kr{\'a}l', Daniel and Oum, Sang-il},
TITLE = {Deciding first order properties of matroids},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {239-250},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dawar-Holm/12,
AUTHOR = {Dawar, Anuj and Holm, Bjarki},
TITLE = {Pebble games with algebraic rules},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {251-262},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kikot-Kontchakov-Podolskii-Zakharyaschev/12,
AUTHOR = {Kikot, Stanislav and Kontchakov, Roman and Podolskii, Vladimir and Zakharyaschev, Michael},
TITLE = {Exponential lower bounds and separation for query rewriting},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {263-274},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kufleitner-Lauser/12a,
AUTHOR = {Kufleitner, Manfred and Lauser, Alexander},
TITLE = {Lattices of logical fragments over words},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {275-286},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {Extended abstract},
}
@incollection{Kuperberg-Vanden_Boom/12,
AUTHOR = {Kuperberg, Denis and Vanden Boom, Michael},
TITLE = {On the expressive power of cost logics over infinite words},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {287-298},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Litak-Pattinson-Sano-Schroder/12,
AUTHOR = {Litak, Tadeusz and Pattinson, Dirk and Sano, Katsuhiko and Schr{\"o}der, Lutz},
TITLE = {Coalgebraic predicate logic},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {299-311},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Murawski-Tzevelekos/12,
AUTHOR = {Murawski, Andrzej S. and Tzevelekos, Nikos},
TITLE = {Algorithmic games for full ground references},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {312-324},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ong-Tsukada/12,
AUTHOR = {Ong, C.-H. Luke and Tsukada, Takeshi},
TITLE = {Two-level game semantics, intersection types, and recursion schemes},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {325-336},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Reddy-Dunphy/12,
AUTHOR = {Reddy, Uday S. and Dunphy, Brian P.},
TITLE = {An automata-theoretic model of idealized Algol},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {337-350},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {Extended abstract},
}
@incollection{Rosu-Stefanescu/12,
AUTHOR = {Ro{\c{s}}u, Grigore and {\c{S}}tef{\v{a}}nescu, Andrei},
TITLE = {Towards a unified theory of operational and axiomatic semantics},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {351-363},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Salvati-Manzonetto-Gehrke-Barendregt/12,
AUTHOR = {Salvati, Sylvain and Manzonetto, Giulio and Gehrke, Mai and Barendregt, Henk},
TITLE = {Loader and Urzyczyn are logically related},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {364-376},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Torunczyk/12,
AUTHOR = {Toru{\'n}czyk, Szymon},
TITLE = {Languages of profinite words and the limitedness problem},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {377-389},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Velner/12,
AUTHOR = {Velner, Yaron},
TITLE = {The complexity of mean-payoff automaton expression},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {390-402},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Barenboim/12,
AUTHOR = {Barenboim, Leonid},
TITLE = {On the locality of some NP-complete problems},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {403-415},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bar-Yehuda-Kantor-Kutten-Rawitz/12,
AUTHOR = {Bar-Yehuda, Reuven and Kantor, Erez and Kutten, Shay and Rawitz, Dror},
TITLE = {Growing half-balls: Minimizing storage and communication costs in CDNs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {416-427},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Berns-Hegeman-Pemmaraju/12,
AUTHOR = {Berns, Andrew and Hegeman, James and Pemmaraju, Sriram V.},
TITLE = {Super-fast distributed algorithms for metric facility location},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {428-439},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bhawalkar-Kleinberg-Lewi-Roughgarden-Sharma/12,
AUTHOR = {Bhawalkar, Kshipra and Kleinberg, Jon and Lewi, Kevin and Roughgarden, Tim and Sharma, Aneesh},
TITLE = {Preventing unraveling in social networks: The anchored $k$-core problem},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {440-451},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chandran-Garay-Ostrovsky/12,
AUTHOR = {Chandran, Nishanth and Garay, Juan and Ostrovsky, Rafail},
TITLE = {Edge fault tolerance on sparse networks},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {452-463},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Deng-Zhang-Zhang/12,
AUTHOR = {Chen, Ning and Deng, Xiaotie and Zhang, Hongyang and Zhang, Jie},
TITLE = {Incentive ratios of Fisher markets},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {464-475},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chiesa-Di_Battista-Erlebach-Patrignani/12,
AUTHOR = {Chiesa, Marco and Di Battista, Giuseppe and Erlebach, Thomas and Patrignani, Maurizio},
TITLE = {Computational complexity of traffic hijacking under BGP and S-BGP},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {476-487},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Diakonikolas-Papadimitriou-Pierrakos-Singer/12,
AUTHOR = {Diakonikolas, Ilias and Papadimitriou, Christos and Pierrakos, George and Singer, Yaron},
TITLE = {Efficiency-revenue trade-offs in auctions},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {488-499},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dieudonne-Pelc/12a,
AUTHOR = {Dieudonn{\'e}, Yoann and Pelc, Andrzej},
TITLE = {Deterministic network exploration by anonymous silent agents with local traffic reports},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {500-512},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elbassioni/12,
AUTHOR = {Elbassioni, Khaled},
TITLE = {A QPTAS for $\epsilon$-envy-free profit-maximizing pricing on line graphs},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {513-524},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fomin-Golovach-Nederlof-Pilipczuk/12,
AUTHOR = {Fomin, Fedor V. and Golovach, Petr and Nederlof, Jesper and Pilipczuk, Micha{\l}},
TITLE = {Minimizing rosenthal potential in multicast games},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {525-536},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gelles-Ostrovsky-Winoto/12,
AUTHOR = {Gelles, Ran and Ostrovsky, Rafail and Winoto, Kina},
TITLE = {Multiparty proximity testing with dishonest majority from equality testing},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {537-548},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goodrich-Mitzenmacher/12,
AUTHOR = {Goodrich, Michael T. and Mitzenmacher, Michael},
TITLE = {Anonymous card shuffling and its applications to parallel mixnets},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {549-560},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Groce-Katz-Thiruvengadam-Zikas/12,
AUTHOR = {Groce, Adam and Katz, Jonathan and Thiruvengadam, Aishwarya and Zikas, Vassilis},
TITLE = {Byzantine agreement with a rational adversary},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {561-572},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gugelmann-Panagiotou-Peter/12,
AUTHOR = {Gugelmann, Luca and Panagiotou, Konstantinos and Peter, Ueli},
TITLE = {Random hyperbolic graphs: Degree sequence and clustering},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {573-585},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {Extended abastract},
}
@incollection{Jain-Menache-Naor-Shepherd/12,
AUTHOR = {Jain, Navendu and Menache, Ishai and Naor, Joseph (Seffi) and Shepherd, F. Bruce},
TITLE = {Topology-aware VM migration in bandwidth oversubscribed datacenter networks},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {586-597},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kane-Mehlhorn-Sauerwald-Sun/12,
AUTHOR = {Kane, Daniel M. and Mehlhorn, Kurt and Sauerwald, Thomas and Sun, He},
TITLE = {Counting arbitrary subgraphs in data streams},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {598-609},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kosowski-Li-Nisse-Suchan/12,
AUTHOR = {Kosowski, Adrian and Li, Bi and Nisse, Nicolas and Suchan, Karol},
TITLE = {$k$-chordal graphs: From cops and robber to compact routing via treewidth},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {610-622},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Koutsoupias-Papakonstantinopoulou/12,
AUTHOR = {Koutsoupias, Elias and Papakonstantinopoulou, Katia},
TITLE = {Contention issues in congestion games},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {623-635},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Krysta-Vocking/12,
AUTHOR = {Krysta, Piotr and V{\"o}cking, Berthold},
TITLE = {Online mechanism design (randomized rounding on the fly)},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {636-647},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ochel-Radke-Vocking/12,
AUTHOR = {Ochel, Marcel and Radke, Klaus and V{\"o}cking, Berthold},
TITLE = {Online packing with gradually improving capacity estimations and applications to network lifetime maximization},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {648-659},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Peleg-Roditty-Tal/12,
AUTHOR = {Peleg, David and Roditty, Liam and Tal, Elad},
TITLE = {Distributed algorithms for network diameter and girth},
BOOKTITLE = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP'2012, Part II (Warwick, UK, July 9-13, 2012)},
SERIES = {LNCS},
VOLUME = {7392},
PAGES = {660-672},
YEAR = {2012},
EDITOR = {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger},
URL = {http://dx.doi.org/10.1007/978-3-642-31585-5_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}