@incollection{Chazelle/07,
AUTHOR = {Chazelle, Bernard},
TITLE = {Ushering in a new era of algorithm design},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {1-1},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Damgard/07,
AUTHOR = {Damg{\aa}rd, Ivan},
TITLE = {A ``proof-reading'' of some issues in cryptography},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {2-11},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schneider/07,
AUTHOR = {Schneider, Fred B.},
TITLE = {Credentials-based authorization: Evaluation and implementation},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {12-14},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dorn-Fomin-Thilikos/07,
AUTHOR = {Dorn, Frederic and Fomin, Fedor V. and Thilikos, Dimitrios M.},
TITLE = {Subexponential parameterized algorithms},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {15-27},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Chan-Pruhs/07,
AUTHOR = {Bansal, Nikhil and Chan, Ho-Leung and Pruhs, Kirk},
TITLE = {Competitive algorithms for due date scheduling},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {28-39},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Christodoulou-Koutsoupias-Kovacs/07,
AUTHOR = {Christodoulou, George and Koutsoupias, Elias and Kov{\'a}cs, Annam{\'a}ria},
TITLE = {Mechanism design for fractional scheduling on unrelated machines},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {40-52},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Motwani-Panigrahy-Xu/07,
AUTHOR = {Motwani, Rajeev and Panigrahy, Rina and Xu, Ying},
TITLE = {Estimating sum by weighted sampling},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {53-64},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Blomer-Naewe/07,
AUTHOR = {Bl{\"o}mer, Johannes and Naewe, Stefanie},
TITLE = {Sampling methods for shortest vectors, closest vectors and successive minima},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {65-77},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pettie/07,
AUTHOR = {Pettie, Seth},
TITLE = {Low distortion spanners},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {78-89},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Berger-Grigni/07,
AUTHOR = {Berger, Andr{\'e} and Grigni, Michelangelo},
TITLE = {Minimum weight 2-edge-connected spanning subgraphs in planar graphs},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {90-101},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Korman/07,
AUTHOR = {Korman, Amos},
TITLE = {Labeling schemes for vertex connectivity},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {102-109},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Iwama-Nishimura-Raymond-Yamashita/07,
AUTHOR = {Iwama, Kazuo and Nishimura, Harumichi and Raymond, Rudy and Yamashita, Shigeru},
TITLE = {Unbounded-error one-way classical and quantum communication complexity},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {110-121},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Montanaro-Winter/07,
AUTHOR = {Montanaro, Ashley and Winter, Andreas},
TITLE = {A lower bound on entanglement-assisted quantum communication complexity},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {122-133},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beame-David-Pitassi-Woelfel/07,
AUTHOR = {Beame, Paul and David, Matei and Pitassi, Toniann and Woelfel, Philipp},
TITLE = {Separating deterministic from nondeterministic NOF multiparty communication complexity},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {134-145},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Demaine-Mozes-Rossman-Weimann/07,
AUTHOR = {Demaine, Erik D. and Mozes, Shay and Rossman, Benjamin and Weimann, Oren},
TITLE = {An optimal decomposition algorithm for tree edit distance},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {146-157},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bosnacki-Elkind-Genest-Peled/07,
AUTHOR = {Bo{\v{s}}na{\v{c}}ki, Dragan and Elkind, Edith and Genest, Blaise and Peled, Doron},
TITLE = {On commutativity based edge lean search},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {158-170},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Katriel-Kenyon-Mathieu-Upfal/07,
AUTHOR = {Katriel, Irit and Kenyon-Mathieu, Claire and Upfal, Eli},
TITLE = {Commitment under uncertainty: Two-stage stochastic matching problems},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {171-182},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lu-Tsai-Wu/07,
AUTHOR = {Lu, Chi-Jen and Tsai, Shi-Chun and Wu, Hsin-Lung},
TITLE = {On the complexity of hard-core set constructions},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {183-194},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{ODonnell-Wimmer/07,
AUTHOR = {O'Donnell, Ryan and Wimmer, Karl},
TITLE = {Approximation by DNF: Examples and counterexamples},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {195-206},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Burgisser-Cucker/07,
AUTHOR = {B{\"u}rgisser, Peter and Cucker, Felipe},
TITLE = {Exotic quantifiers, complexity classes, and complete problems},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {207-218},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bar-Noy-Cheilaris-Olonetsky-Smorodinsky/07,
AUTHOR = {Bar-Noy, Amotz and Cheilaris, Panagiotis and Olonetsky, Svetlana and Smorodinsky, Shakhar},
TITLE = {Online conflict-free colorings for hypergraphs},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {219-230},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fraigniaud-Gavoille-Ilcinkas-Pelc/07,
AUTHOR = {Fraigniaud, Pierre and Gavoille, Cyril and Ilcinkas, David and Pelc, Andrzej},
TITLE = {Distributed computing with advice: Information sensitivity of graph coloring},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {231-242},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ishai-Malkin-Strauss-Wright/07,
AUTHOR = {Ishai, Yuval and Malkin, Tal and Strauss, Martin J. and Wright, Rebecca N.},
TITLE = {Private multiparty sampling and approximation of vector combinations},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {243-254},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dedic-Mohassel/07,
AUTHOR = {Dedic, Nenad and Mohassel, Payman},
TITLE = {Constant-round private database queries},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {255-266},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Larose-Tesson/07,
AUTHOR = {Larose, Beno{\^{i}}t and Tesson, Pascal},
TITLE = {Universal algebra and hardness results for constraint satisfaction problems},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {267-278},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Atserias-Bulatov-Dalmau/07,
AUTHOR = {Atserias, Albert and Bulatov, Andrei and Dalmau, Victor},
TITLE = {On the power of $k$-consistency},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {279-290},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dershowitz-Tzameret/07,
AUTHOR = {Dershowitz, Nachum and Tzameret, Iddo},
TITLE = {Complexity of propositional proofs under a promise},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {291-302},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Moran-Naor-Segev/07,
AUTHOR = {Moran, Tal and Naor, Moni and Segev, Gil},
TITLE = {Deterministic history-independent strategies for storing information on write-once memories},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {303-315},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kiayias-Zhou/07,
AUTHOR = {Kiayias, Aggelos and Zhou, Hong-Sheng},
TITLE = {Trading static for adaptive security in universally composable zero-knowledge},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {316-327},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kapron-Malka-Srinivasan/07,
AUTHOR = {Kapron, Bruce and Malka, Lior and Srinivasan, Venkatesh},
TITLE = {A characterization of non-interactive instance-dependent commitment-schemes (NIC)},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {328-339},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fellows-Fertin-Hermelin-Vialette/07,
AUTHOR = {Fellows, Michael R. and Fertin, Guillaume and Hermelin, Danny and Vialette, St{\'e}phane},
TITLE = {Sharp tractability borderlines for finding connected motifs in vertex-colored graphs},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {340-351},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alon-Fomin-Gutin-Krivelevich-Saurabh/07,
AUTHOR = {Alon, Noga and Fomin, Fedor V. and Gutin, Gregory and Krivelevich, Michael and Saurabh, Saket},
TITLE = {Parameterized algorithms for directed maximum leaf problems},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {352-362},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Grohe-Gruber/07,
AUTHOR = {Grohe, Martin and Gr{\"u}ber, Magdalena},
TITLE = {Parameterized approximability of the disjoint cycle problem},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {363-374},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guo-Niedermeier/07,
AUTHOR = {Guo, Jiong and Niedermeier, Rolf},
TITLE = {Linear problem kernels for $NP$-hard problems on planar graphs},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {375-386},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ostrovsky-Pandey-Sahai/07,
AUTHOR = {Ostrovsky, Rafail and Pandey, Omkant and Sahai, Amit},
TITLE = {Private locally decodable codes},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {387-398},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bellare-Ristenpart/07,
AUTHOR = {Bellare, Mihir and Ristenpart, Thomas},
TITLE = {Hash functions in the dedicated-key setting: Design choices and MPP transforms},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {399-410},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bellare-Namprempre-Neven/07,
AUTHOR = {Bellare, Mihir and Namprempre, Chanathip and Neven, Gregory},
TITLE = {Unrestricted aggregate signatures},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {411-422},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chandran-Groth-Sahai/07,
AUTHOR = {Chandran, Nishanth and Groth, Jens and Sahai, Amit},
TITLE = {Ring signatures of sub-linear size without random oracles},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {423-434},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alon-Gutner/07,
AUTHOR = {Alon, Noga and Gutner, Shai},
TITLE = {Balanced families of perfect hash functions and their applications},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {435-446},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Caragiannis-Flammini-Moscardelli/07,
AUTHOR = {Caragiannis, Ioannis and Flammini, Michele and Moscardelli, Luca},
TITLE = {An exponential improvement on the MST heuristic for minimum energy broadcasting in ad hoc wireless networks},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {447-458},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schroder-Pattinson/07a,
AUTHOR = {Schr{\"o}der, Lutz and Pattinson, Dirk},
TITLE = {Modular algorithms for heterogeneous modal logics},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {459-471},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Simon-Bansal-Mallya-Gupta/07,
AUTHOR = {Simon, Luke and Bansal, Ajay and Mallya, Ajay and Gupta, Gopal},
TITLE = {Co-logic programming: Extending logic programming with coinduction},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {472-483},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Adida-Wikstrom/07,
AUTHOR = {Adida, Ben and Wikstr{\"o}m, Douglas},
TITLE = {Offline/online mixing},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {484-495},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Furukawa-Attrapadung/07,
AUTHOR = {Furukawa, Jun and Attrapadung, Nuttapong},
TITLE = {Fully collusion resistant black-box traitor revocable broadcast encryption with short private keys},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {496-508},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{He-Munro-Rao/07,
AUTHOR = {He, Meng and Munro, J. Ian and Rao, S. Srinivasa},
TITLE = {Succinct ordinal trees based on tree covering},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {509-520},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Hon-Shah-Vitter/07,
AUTHOR = {Gupta, Ankur and Hon, Wing-Kai and Shah, Rahul and Vitter, Jeffrey Scott},
TITLE = {A framework for dynamizing succinct data structures},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {521-532},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Franceschini-Muthukrishnan/07,
AUTHOR = {Franceschini, Gianni and Muthukrishnan, S.},
TITLE = {In-place suffix sorting},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {533-545},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bodirsky-Chen-Kara-von_Oertzen/07,
AUTHOR = {Bodirsky, Manuel and Chen, Hubie and K{\'a}ra, Jan and von Oertzen, Timo},
TITLE = {Maximal infinite-valued constraint languages},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {546-557},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Atserias-Bulatov-Dawar/07,
AUTHOR = {Atserias, Albert and Bulatov, Andrei and Dawar, Anuj},
TITLE = {Affine systems of equations and counting infinitary logic},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {558-570},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kreutzer-Otto-Schweikardt/07,
AUTHOR = {Kreutzer, Stephan and Otto, Martin and Schweikardt, Nicole},
TITLE = {Boundedness of monadic FO over acyclic structures},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {571-582},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiat-Kaplan-Levy-Olonetsky/07,
AUTHOR = {Fiat, Amos and Kaplan, Haim and Levy, Meital and Olonetsky, Svetlana},
TITLE = {Strong price of anarchy for machine load balancing},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {583-594},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kontogiannis-Spirakis/07,
AUTHOR = {Kontogiannis, Spyros C. and Spirakis, Paul G.},
TITLE = {Efficient algorithms for constant well supported approximate equilibria in bimatrix games},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {595-606},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiore-Hur/07,
AUTHOR = {Fiore, Marcelo and Hur, Chung-Kil},
TITLE = {Equational systems and free constructions},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {607-618},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hasuo-Jacobs-Uustalu/07,
AUTHOR = {Hasuo, Ichiro and Jacobs, Bart and Uustalu, Tarmo},
TITLE = {Categorical views on computations on trees},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {619-630},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cai-Lu/07a,
AUTHOR = {Cai, Jin-Yi and Lu, Pinyan},
TITLE = {Holographic algorithms: The power of dimensionality resolved},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {631-642},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bienvenu-Merkle/07,
AUTHOR = {Bienvenu, Laurent and Merkle, Wolfgang},
TITLE = {Reconciling data compression and Kolmogorov complexity},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {643-654},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Miller-Phillips-Sheehy/07,
AUTHOR = {Miller, Gary L. and Phillips, Todd and Sheehy, Donald},
TITLE = {Size competitive meshing without large angles},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {655-666},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Laird/07,
AUTHOR = {Laird, James},
TITLE = {A fully abstract trace semantics for general references},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {667-679},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lee-Palsberg-Pereira/07,
AUTHOR = {Lee, Jonathan K. and Palsberg, Jens and Pereira, Fernando Magno Quint{\~a}o},
TITLE = {Aliased register allocation for straight-line programs is $NP$-complete},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {680-691},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_59},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schmitz/07,
AUTHOR = {Schmitz, Sylvain},
TITLE = {Conservative ambiguity detection in context-free grammars},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {692-703},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guha-McGregor/07,
AUTHOR = {Guha, Sudipto and McGregor, Andrew},
TITLE = {Lower bounds for quantile estimation in random-order and multi-pass streaming},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {704-715},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_61},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elkin/07,
AUTHOR = {Elkin, Michael},
TITLE = {Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {716-727},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_62},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chu-Kannan-McGregor/07,
AUTHOR = {Chu, Matthew and Kannan, Sampath and McGregor, Andrew},
TITLE = {Checking and spot-checking the correctness of priority queues},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {728-739},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_63},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kobayashi-Suto/07,
AUTHOR = {Kobayashi, Naoki and Suto, Takashi},
TITLE = {Undecidability of 2-label BPP equivalences and behavioral type systems for the $\pi$-calculus},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {740-751},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_64},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Luttgen-Vogler/07,
AUTHOR = {L{\"u}ttgen, Gerald and Vogler, Walter},
TITLE = {Ready simulation for concurrency: It's logical!},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {752-763},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_65},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goubault-Larrecq/07,
AUTHOR = {Goubault-Larrecq, Jean},
TITLE = {Continuous capacities on continuous state spaces},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {764-776},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_66},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Coja-Oghlan-Panagiotou-Steger/07,
AUTHOR = {Coja-Oghlan, Amin and Panagiotou, Konstantinos and Steger, Angelika},
TITLE = {On the chromatic number of random graphs},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {777-788},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_67},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alon-Coja-Oghlan-Han-Kang-Rodl-Schacht/07,
AUTHOR = {Alon, Noga and Coja-Oghlan, Amin and H{\`a}n, Hi{\d{\^e}}p and Kang, Mihyun and R{\"o}dl, Vojt{\v{e}}ch and Schacht, Mathias},
TITLE = {Quasi-randomness and algorithmic regularity for graphs with general degree distributions},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {789-800},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_68},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Blaser-Dell/07,
AUTHOR = {Bl{\"a}ser, Markus and Dell, Holger},
TITLE = {Complexity of the cover polynomial},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {801-812},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_69},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Boigelot-Brusten/07,
AUTHOR = {Boigelot, Bernard and Brusten, Julien},
TITLE = {A generalization of Cobham's theorem to automata over real numbers},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {813-824},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_70},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brihaye-Henzinger-Prabhu-Raskin/07,
AUTHOR = {Brihaye, Thomas and Henzinger, Thomas A. and Prabhu, Vinayak S. and Raskin, Jean-Fran{\c{c}}ois},
TITLE = {Minimum-time reachability in timed games},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {825-837},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_71},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jurdzinski-Trivedi/07,
AUTHOR = {Jurdzi{\'n}ski, Marcin and Trivedi, Ashutosh},
TITLE = {Reachability-time games on timed automata},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {838-849},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_72},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gimbert-Zielonka/07,
AUTHOR = {Gimbert, Hugo and Zielonka, Wies{\l}aw},
TITLE = {Perfect information stochastic priority games},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {850-861},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_73},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bjorklund-Bojanczyk/07,
AUTHOR = {Bj{\"o}rklund, Henrik and Boja{\'n}czyk, Miko{\l}aj},
TITLE = {Bounded depth data trees},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {862-874},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_74},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Karianto-Loding/07,
AUTHOR = {Karianto, Wong and L{\"o}ding, Christof},
TITLE = {Unranked tree automata with sibling equalities and disequalities},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {875-887},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_75},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arenas-Barcelo-Libkin/07,
AUTHOR = {Arenas, Marcelo and Barcel{\'o}, Pablo and Libkin, Leonid},
TITLE = {Regular languages of nested words: Fixed points, automata, and synchronization},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {888-900},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_76},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Colcombet/07,
AUTHOR = {Colcombet, Thomas},
TITLE = {A combinatorial theorem for trees --- Applications to monadic logic and infinite structures},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {901-912},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_77},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dawar-Grohe-Kreutzer-Schweikardt/07,
AUTHOR = {Dawar, Anuj and Grohe, Martin and Kreutzer, Stephan and Schweikardt, Nicole},
TITLE = {Model theory makes formulas large},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {913-924},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_78},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bozzelli-La_Torre/07,
AUTHOR = {Bozzelli, Laura and La Torre, Salvatore},
TITLE = {Decision problems for lower/upper bound parametric timed automata},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {925-936},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_79},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{La_Torre-Parlato/07,
AUTHOR = {La Torre, Salvatore and Parlato, Gennaro},
TITLE = {On the complexity of LTL model-checking of recursive state machines},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {937-948},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_80},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cary-Rudra-Sabharwal/07,
AUTHOR = {Cary, Matthew and Rudra, Atri and Sabharwal, Ashish},
TITLE = {Paper retraction: On the hardness of embeddings between two finite metrics},
BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP'2007 (Wroc{\l}aw, Poland, July 9-13, 2007)},
SERIES = {LNCS},
VOLUME = {4596},
PAGES = {949-949},
YEAR = {2007},
EDITOR = {Arge, Lars and Cachin, Christian and Jurdzi{\'n}ski, Tomasz and Tarlecki, Andrzej},
URL = {http://dx.doi.org/10.1007/978-3-540-73420-8_81},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}