@incollection{Kleinberg/13a, AUTHOR = {Kleinberg, Jon}, TITLE = {Algorithms, networks, and social phenomena}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {1-3}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_1}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Albers/13a, AUTHOR = {Albers, Susanne}, TITLE = {Recent advances for a classical scheduling problem}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {4-14}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_2}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Almagor-Boker-Kupferman/13, AUTHOR = {Almagor, Shaull and Boker, Udi and Kupferman, Orna}, TITLE = {Formalizing and reasoning about quality}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {15-27}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_3}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Marx/13b, AUTHOR = {Marx, D{\'a}niel}, TITLE = {The square root phenomenon in planar graphs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {28-28}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_4}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Spirakis-Nikoletseas-Raptopoulos/13, AUTHOR = {Spirakis, Paul G. and Nikoletseas, Sotiris and Raptopoulos, Christoforos}, TITLE = {A guided tour in random intersection graphs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {29-35}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_5}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Widmayer/13, AUTHOR = {Widmayer, Peter}, TITLE = {To be uncertain is uncomfortable, but to be certain is ridiculous}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {36-36}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_6}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Alur-Raghothaman/13, AUTHOR = {Alur, Rajeev and Raghothaman, Mukund}, TITLE = {Decision problems for additive regular functions}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {37-48}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_7}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Barthe-Olmedo/13, AUTHOR = {Barthe, Gilles and Olmedo, Federico}, TITLE = {Beyond differential privacy: Composition theorems and relational logic for $f$-divergences between probabilistic programs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {49-60}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_8}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Basset/13, AUTHOR = {Basset, Nicolas}, TITLE = {A maximal entropy stochastic process for a timed automaton}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {61-73}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_9}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Benaim-Benedikt-Charatonik-Kieronski-Lenhardt-Mazowiecki-Worell/13, AUTHOR = {Benaim, Saguy and Benedikt, Michael and Charatonik, Witold and Kiero{\'n}ski, Emanuel and Lenhardt, Rastislav and Mazowiecki, Philip and Worell, James}, TITLE = {Complexity of two-variable logic on finite trees}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {74-88}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_10}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Boker-Kuperberg-Kupferman-Skrzypczak/13, AUTHOR = {Boker, Udi and Kuperberg, Denis and Kupferman, Orna and Skrzypczak, Micha{\l}}, TITLE = {Nondeterminism in the presence of a diverse or unknown future}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {89-100}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_11}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Carreiro-Gorin-Schroder/13, AUTHOR = {Carreiro, Facundo and Gor{\'{i}}n, Daniel and Schr{\"o}der, Lutz}, TITLE = {Coalgebraic announcement logics}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {101-112}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_12}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Charlier-Kamae-Puzynina-Zamboni/13, AUTHOR = {Charlier, {\'E}milie and Kamae, Teturo and Puzynina, Svetlana and Zamboni, Luca Q.}, TITLE = {Self-shuffling words}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {113-124}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_13}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Chen-Marx/13, AUTHOR = {Chen, Hubie and Marx, D{\'a}niel}, TITLE = {Block-sorted quantified conjunctive queries}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {125-136}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_14}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Chretien-Cortier-Delaune/13, AUTHOR = {Chr{\'e}tien, R{\'e}my and Cortier, V{\'e}ronique and Delaune, St{\'e}phanie}, TITLE = {From security protocols to pushdown automata}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {137-149}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_15}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Czerwinski-Martens-Masopust/13, AUTHOR = {Czerwi{\'n}ski, Wojciech and Martens, Wim and Masopust, Tom{\'a}{\v{s}}}, TITLE = {Efficient separability of regular languages by subsequences and suffixes}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {150-161}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_16}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Demri-Dhar-Sangnier/13, AUTHOR = {Demri, St{\'e}phane and Dhar, Amit Kumar and Sangnier, Arnaud}, TITLE = {On the complexity of verifying regular properties on flat counter systems}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {162-173}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_17}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Denielou-Yoshida/13, AUTHOR = {Deni{\'e}lou, Pierre-Malo and Yoshida, Nobuko}, TITLE = {Multiparty compatibility in communicating automata: Characterisation and synthesis of global session types}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {174-186}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_18}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Di_Cosmo-Mauro-Zacchiroli-Zavattaro/13, AUTHOR = {Di Cosmo, Roberto and Mauro, Jacopo and Zacchiroli, Stefano and Zavattaro, Gianluigi}, TITLE = {Component reconfiguration in the presence of conflicts}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {187-198}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_19}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Etessami-Stewart-Yannakakis/13, AUTHOR = {Etessami, Kousha and Stewart, Alistair and Yannakakis, Mihalis}, TITLE = {Stochastic context-free grammars, regular languages, and Newton's method}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {199-211}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_20}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Fearnley-Jurdzinski/13, AUTHOR = {Fearnley, John and Jurdzi{\'n}ski, Marcin}, TITLE = {Reachability in two-clock timed automata is PSPACE-complete}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {212-223}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_21}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Friedmann-Klaedtke-Lange/13, AUTHOR = {Friedmann, Oliver and Klaedtke, Felix and Lange, Martin}, TITLE = {Ramsey goes visibly pushdown}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {224-237}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_22}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Fu/13, AUTHOR = {Fu, Yuxi}, TITLE = {Checking equality and regularity for normed BPA with silent moves}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {238-249}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_23}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Ganian-Hlineny-Kral-Obdrzalek-Schwartz-Teska/13, AUTHOR = {Ganian, Robert and Hlin{\v{e}}n{\'y}, Petr and Kr{\'a}l', Daniel and Obdr{\v{z}}{\'a}lek, Jan and Schwartz, Jarett and Teska, Jakub}, TITLE = {Fo model checking of interval graphs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {250-262}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_24}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Gelderie/13, AUTHOR = {Gelderie, Marcus}, TITLE = {Strategy composition in compositional games}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {263-274}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_25}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Genest-Gimbert-Muscholl-Walukiewicz/13, AUTHOR = {Genest, Blaise and Gimbert, Hugo and Muscholl, Anca and Walukiewicz, Igor}, TITLE = {Asynchronous games over tree architectures}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {275-286}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_26}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Gottlob-Pieris-Tendera/13, AUTHOR = {Gottlob, Georg and Pieris, Andreas and Tendera, Lidia}, TITLE = {Querying the guarded fragment with transitivity}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {287-298}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_27}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Im-Nakata-Park/13, AUTHOR = {Im, Hyeonseung and Nakata, Keiko and Park, Sungwoo}, TITLE = {Contractive signatures with recursive types, type parameters, and abstract types}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {299-311}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_28}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Janin/13, AUTHOR = {Janin, David}, TITLE = {Algebras, automata and logic for languages of labeled birooted trees}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {312-323}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_29}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Jez/13b, AUTHOR = {Je{\.z}, Artur}, TITLE = {One-variable word equations in linear time}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {324-335}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_30}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Kobele-Salvati/13, AUTHOR = {Kobele, Gregory M. and Salvati, Sylvain}, TITLE = {The IO and OI hierarchies revisited}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {336-348}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_31}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Leivant-Marion/13, AUTHOR = {Leivant, Daniel and Marion, Jean-Yves}, TITLE = {Evolving graph-structures and their implicit computational complexity}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {349-360}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_32}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Lohrey-Steinberg-Zetzsche/13, AUTHOR = {Lohrey, Markus and Steinberg, Benjamin and Zetzsche, Georg}, TITLE = {Rational subsets and submonoids of wreath products}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {361-372}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_33}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Padovani/13, AUTHOR = {Padovani, Luca}, TITLE = {Fair subtyping for open session types}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {373-384}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_34}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Petricek-Orchard-Mycroft/13, AUTHOR = {Petricek, Tomas and Orchard, Dominic and Mycroft, Alan}, TITLE = {Coeffects: Unified static analysis of context-dependence}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {385-397}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_35}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Stirling/13, AUTHOR = {Stirling, Colin}, TITLE = {Proof systems for retracts in simply typed lambda calculus}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {398-409}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_36}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Woods/13, AUTHOR = {Woods, Kevin}, TITLE = {Presburger arithmetic, rational generating functions, and quasi-polynomials}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {410-421}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_37}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Worrell/13, AUTHOR = {Worrell, James}, TITLE = {Revisiting the equivalence problem for finite multitape automata}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {422-433}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_38}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Zetzsche/13, AUTHOR = {Zetzsche, Georg}, TITLE = {Silent transitions in automata with storage}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {434-445}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_39}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Albers-Passen/13, AUTHOR = {Albers, Susanne and Passen, Achim}, TITLE = {New online algorithms for story scheduling in web advertising}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {446-458}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_40}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Bachrach-Porat/13, AUTHOR = {Bachrach, Yoram and Porat, Ely}, TITLE = {Sketching for big data recommender systems using fast pseudo-random fingerprints}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {459-471}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_41}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Becchetti-Bonifaci-Dirnberger-Karrenbauer-Mehlhorn/13, AUTHOR = {Becchetti, Luca and Bonifaci, Vincenzo and Dirnberger, Michael and Karrenbauer, Andreas and Mehlhorn, Kurt}, TITLE = {Physarum can compute shortest paths: Convergence proofs and complexity bounds}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {472-483}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_42}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Celis-Gklezakos-Karlin/13, AUTHOR = {Celis, L. Elisa and Gklezakos, Dimitrios C. and Karlin, Anna R.}, TITLE = {On revenue maximization for agents with costly information acquisition}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {484-495}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_43}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, PCOMMENT = {extended abstract}, } @incollection{Christodoulou-Gairing/13, AUTHOR = {Christodoulou, George and Gairing, Martin}, TITLE = {Price of stability in polynomial congestion games}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {496-507}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_44}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Czyzowicz-Kranakis-Pacheco/13, AUTHOR = {Czyzowicz, Jurek and Kranakis, Evangelos and Pacheco, Eduardo}, TITLE = {Localization for a system of colliding robots}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {508-519}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_45}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Dereniowski-Disser-Kosowski-Pajak-Uznanski/13, AUTHOR = {Dereniowski, Dariusz and Disser, Yann and Kosowski, Adrian and Paj{\c{a}}k, Dominik and Uzna{\'n}ski, Przemys{\l}aw}, TITLE = {Fast collaborative graph exploration}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {520-532}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_46}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Dieudonne-Pelc/13, AUTHOR = {Dieudonn{\'e}, Yoann and Pelc, Andrzej}, TITLE = {Deterministic polynomial approach in the plane}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {533-544}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_47}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Faust-Hazay-Venturi/13, AUTHOR = {Faust, Sebastian and Hazay, Carmit and Venturi, Daniele}, TITLE = {Outsourced pattern matching}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {545-556}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_48}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Fusco-Pelc-Petreschi/13, AUTHOR = {Fusco, Emanuele G. and Pelc, Andrzej and Petreschi, Rossella}, TITLE = {Learning a ring cheaply and fast}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {557-568}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_49}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Gravin-Lu/13, AUTHOR = {Gravin, Nick and Lu, Pinyan}, TITLE = {Competitive auctions for markets with positive externalities}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {569-580}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_50}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Harris-Morsy-Pandurangan-Robinson-Srinivasan/13, AUTHOR = {Harris, David G. and Morsy, Ehab and Pandurangan, Gopal and Robinson, Peter and Srinivasan, Aravind}, TITLE = {Efficient computation of balanced structures}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {581-593}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_51}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Hartung-Nichterlein-Niedermeier-Suchy/13, AUTHOR = {Hartung, Sepp and Nichterlein, Andr{\'e} and Niedermeier, Rolf and Such{\'y}, Ond{\v{r}}ej}, TITLE = {A refined complexity analysis of degree anonymization in graphs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {594-606}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_52}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Henzinger-Krinninger-Nanongkai/13, AUTHOR = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon}, TITLE = {Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {607-619}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_53}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Hoefer-Wagner/13, AUTHOR = {Hoefer, Martin and Wagner, Lisa}, TITLE = {Locally stable marriage with strict preferences}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {620-631}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_54}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Jurdzinski-Kowalski-Stachowiak/13, AUTHOR = {Jurdzinski, Tomasz and Kowalski, Dariusz R. and Stachowiak, Grzegorz}, TITLE = {Distributed deterministic broadcasting in wireless networks of weak devices}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {632-644}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_55}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Lipmaa-Toft/13, AUTHOR = {Lipmaa, Helger and Toft, Tomas}, TITLE = {Secure equality and greater-than tests with sublinear online complexity}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {645-656}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_56}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Mertzios-Michail-Chatzigiannakis-Spirakis/13, AUTHOR = {Mertzios, George B. and Michail, Othon and Chatzigiannakis, Ioannis and Spirakis, Paul G.}, TITLE = {Temporal network optimization subject to connectivity constraints}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {657-668}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_57}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Mertzios-Spirakis/13, AUTHOR = {Mertzios, George B. and Spirakis, Paul G.}, TITLE = {Strong bounds for evolution in networks}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {669-680}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_58}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, } @incollection{Pettie-Su/13, AUTHOR = {Pettie, Seth and Su, Hsin-Hao}, TITLE = {Fast distributed coloring algorithms for triangle-free graphs}, BOOKTITLE = {Proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP'2013, Part II (Riga, Latvia, July 8-12, 2013)}, SERIES = {LNCS}, VOLUME = {7966}, PAGES = {681-693}, YEAR = {2013}, EDITOR = {Fomin, Fedor, V. and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David}, URL = {http://dx.doi.org/10.1007/978-3-642-39212-2_59}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin-Heidelberg}, }