@incollection{Valiant/05,
AUTHOR = {Valiant, Leslie G.},
TITLE = {Holographic circuits},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1-15},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Datta-Derek-Mitchell-Shmatikov-Turuani/05,
AUTHOR = {Datta, Anupam and Derek, Ante and Mitchell, John C. and Shmatikov, Vitaly and Turuani, Mathieu},
TITLE = {Probabilistic polynomial-time semantics for a protocol security logic},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {16-29},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Castagna-Frisch/05,
AUTHOR = {Castagna, Giuseppe and Frisch, Alain},
TITLE = {A gentle introduction to semantic subtyping},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {30-34},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Libkin/05,
AUTHOR = {Libkin, Leonid},
TITLE = {Logics for unranked trees: An overview},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {35-50},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gairing-Lucking-Monien-Tiemann/05,
AUTHOR = {Gairing, Martin and L{\"u}cking, Thomas and Monien, Burkhard and Tiemann, Karsten},
TITLE = {Nash equilibria, the price of anarchy and the fully mixed Nash equilibrium conjecture},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {51-65},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bille-Gortz/05,
AUTHOR = {Bille, Philip and G{\o}rtz, Inge Li},
TITLE = {The tree inclusion problem: In optimal space and faster},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {66-77},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alstrup-Gortz-Rauhe-Thorup-Zwick/05,
AUTHOR = {Alstrup, Stephen and G{\o}rtz, Inge Li and Rauhe, Theis and Thorup, Mikkel and Zwick, Uri},
TITLE = {Union-find with constant time deletions},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {78-89},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Franceschini-Grossi/05,
AUTHOR = {Franceschini, Gianni and Grossi, Roberto},
TITLE = {Optimal in-place sorting of vectors and records},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {90-102},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kaligosi-Mehlhorn-Munro-Sanders/05,
AUTHOR = {Kaligosi, Kanela and Mehlhorn, Kurt and Munro, J. Ian and Sanders, Peter},
TITLE = {Towards optimal multiple selection},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {103-114},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Zimand/05,
AUTHOR = {Zimand, Marius},
TITLE = {Simple extractors via constructions of cryptographic pseudo-random generators},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {115-127},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Horvitz-Katz/05,
AUTHOR = {Horvitz, Omer and Katz, Jonathan},
TITLE = {Bounds on the efficiency of ''black-box'' commitment schemes},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {128-139},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wee/05,
AUTHOR = {Wee, Hoeteck},
TITLE = {On round-efficient argument systems},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {140-152},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Tamassia-Triandopoulos/05,
AUTHOR = {Tamassia, Roberto and Triandopoulos, Nikos},
TITLE = {Computational bounds on hierarchical data processing with applications to information security},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {153-165},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dietzfelbinger-Weidling/05,
AUTHOR = {Dietzfelbinger, Martin and Weidling, Christoph},
TITLE = {Balanced allocation and dictionaries with tightly packed constant size bins},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {166-178},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chiniforooshan-Farzan-Mirzazadeh/05,
AUTHOR = {Chiniforooshan, Ehsan and Farzan, Arash and Mirzazadeh, Mehdi},
TITLE = {Worst case optimal union-intersection expression evaluation},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {179-190},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fomin-Grandoni-Kratsch/05,
AUTHOR = {Fomin, Fedor V. and Grandoni, Fabrizio and Kratsch, Dieter},
TITLE = {Measure and conquer: Domination --- A case study},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {191-203},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kursawe-Shoup/05,
AUTHOR = {Kursawe, Klaus and Shoup, Victor},
TITLE = {Optimistic asynchronous atomic broadcast},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {204-215},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Di_Crescenzo-Kiayias/05,
AUTHOR = {Di Crescenzo, Giovanni and Kiayias, Aggelos},
TITLE = {Asynchronous perfectly secure communication over one-time pads},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {216-227},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Persiano-Visconti/05,
AUTHOR = {Persiano, Giuseppe and Visconti, Ivan},
TITLE = {Single-prover concurrent zero knowledge in almost constant rounds},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {228-240},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kowaluk-Lingas/05,
AUTHOR = {Kowaluk, Miroslaw and Lingas, Andrzej},
TITLE = {LCA queries in directed acyclic graphs},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {241-248},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Roditty-Zwick/05,
AUTHOR = {Roditty, Liam and Zwick, Uri},
TITLE = {Replacement paths and $k$ simple shortest paths in unweighted directed graphs},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {249-260},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Roditty-Thorup-Zwick/05,
AUTHOR = {Roditty, Liam and Thorup, Mikkel and Zwick, Uri},
TITLE = {Deterministic constructions of approximate distance oracles and spanners},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {261-272},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kavitha/05,
AUTHOR = {Kavitha, Telikepalli},
TITLE = {An ${\~O}(m^2n)$ randomized algorithm to compute a minimum cycle basis of a directed graph},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {273-284},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Moran-Naor/05,
AUTHOR = {Moran, Tal and Naor, Moni},
TITLE = {Basing cryptographic protocols on tamper-evident seals},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {285-297},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Catalano-Visconti/05,
AUTHOR = {Catalano, Dario and Visconti, Ivan},
TITLE = {Hybrid trapdoor commitments and their applications},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {298-310},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hopper/05,
AUTHOR = {Hopper, Nicholas},
TITLE = {On steganographic chosen covertext security},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {311-323},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Braeken-Borissov-Nikova-Preneel/05,
AUTHOR = {Braeken, An and Borissov, Yuri and Nikova, Svetla and Preneel, Bart},
TITLE = {Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {324-334},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cohen-Fraigniaud-Ilcinkas-Korman-Peleg/05,
AUTHOR = {Cohen, Reuven and Fraigniaud, Pierre and Ilcinkas, David and Korman, Amos and Peleg, David},
TITLE = {Label-guided graph exploration by a finite automaton},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {335-346},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chlebus-Gasieniec-Kowalski-Radzik/05,
AUTHOR = {Chlebus, Bogdan S. and G{\c{a}}sieniec, Leszek and Kowalski, Dariusz R. and Radzik, Tomasz},
TITLE = {On the wake-up problem in radio networks},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {347-359},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiala-Golovach-Kratochvil/05,
AUTHOR = {Fiala, Ji{\v{r}}{\'{i}} and Golovach, Petr A. and Kratochv{\'{i}}l, Jan},
TITLE = {Distance constrained labelings of graphs of bounded treewidth},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {360-372},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gu-Tamaki/05,
AUTHOR = {Gu, Qian-Ping and Tamaki, Hisao},
TITLE = {Optimal branch-decomposition of planar graphs in $O(n^3)$ time},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {373-384},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hromkovic-Schnitger/05,
AUTHOR = {Hromkovi{\v{c}}, Juraj and Schnitger, Georg},
TITLE = {NFAs with and without $\epsilon$-transitions},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {385-396},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beal-Lombardy-Sakarovitch/05,
AUTHOR = {B{\'e}al, Marie-Pierre and Lombardy, Sylvain and Sakarovitch, Jacques},
TITLE = {On the equivalence of $Z$-automata},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {397-409},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Czeizler-Kari/05,
AUTHOR = {Czeizler, Eugen and Kari, Jarkko},
TITLE = {A tight linear bound on the neighborhood of inverse cellular automata},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {410-420},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beaudry-Lemieux-Therien/05,
AUTHOR = {Beaudry, Martin and Lemieux, Fran{\c{c}}ois and Th{\'e}rien, Denis},
TITLE = {Groupoids that recognize only regular languages},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {421-433},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kiltz-Mityagin-Panjwani-Raghavan/05,
AUTHOR = {Kiltz, Eike and Mityagin, Anton and Panjwani, Saurabh and Raghavan, Barath},
TITLE = {Append-only signatures},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {434-445},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Trolin-Wikstrom/05,
AUTHOR = {Trolin, M{\aa}rten and Wikstr{\"o}m, Douglas},
TITLE = {Hierarchical group signatures},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {446-458},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lipmaa-Wang-Bao/05,
AUTHOR = {Lipmaa, Helger and Wang, Guilin and Bao, Feng},
TITLE = {Designated verifier signature schemes: Attacks, new security notions and a new construction},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {459-471},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Maurer-Sjodin/05,
AUTHOR = {Maurer, Ueli and Sj{\"o}din, Johan},
TITLE = {Single-key AIL-MACs from any FIL-MAC},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {472-484},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Zhang/05b,
AUTHOR = {Zhang, Li},
TITLE = {The efficiency and fairness of a fixed budget resource allocation game},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {485-496},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lin-Roughgarden-Tardos-Walkover/05,
AUTHOR = {Lin, Henry and Roughgarden, Tim and Tardos, {\'E}va and Walkover, Asher},
TITLE = {Braess's paradox, Fibonacci numbers, and exponential inapproximability},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {497-512},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Droste-Gastin/05,
AUTHOR = {Droste, Manfred and Gastin, Paul},
TITLE = {Weighted automata and weighted logics},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {513-525},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Tesson-Therien/05,
AUTHOR = {Tesson, Pascal and Th{\'e}rien, Denis},
TITLE = {Restricted two-variable $FO+MOD$ sentences, circuits and communication complexity},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {526-538},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Haneda-Kawazoe-Takahashi/05,
AUTHOR = {Haneda, Mitsuhiro and Kawazoe, Mitsuru and Takahashi, Tetsuya},
TITLE = {Suitable curves for genus-4 HCC over prime fields: Point counting formulae for hyperelliptic curves of type $y^2 = x^{2k+1} + ax$},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {539-550},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kayal/05,
AUTHOR = {Kayal, Neeraj},
TITLE = {Solvability of a system of bivariate polynomial equations over a finite field},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {551-562},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jampala-Zeh/05,
AUTHOR = {Jampala, Hema and Zeh, Norbert},
TITLE = {Cache-oblivious planar shortest paths},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {563-575},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brodal-Fagerberg-Moruz/05,
AUTHOR = {Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Moruz, Gabriel},
TITLE = {Cache-aware and cache-oblivious adaptive sorting},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {576-588},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wegener/05,
AUTHOR = {Wegener, Ingo},
TITLE = {Simulated annealing beats metropolis in combinatorial optimization},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {589-601},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Epstein-Levy/05,
AUTHOR = {Epstein, Leah and Levy, Meital},
TITLE = {Online interval coloring and variants},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {602-613},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chan-Lam-Wong/05,
AUTHOR = {Chan, Wun-Tat and Lam, Tak-Wah and Wong, Prudence W.H.},
TITLE = {Dynamic bin packing of unit fractions items},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {614-626},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Englert-Westermann/05,
AUTHOR = {Englert, Matthias and Westermann, Matthias},
TITLE = {Reordering buffer management for non-uniform cost models},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {627-638},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chevalier-Rusinowitch/05,
AUTHOR = {Chevalier, Yannick and Rusinowitch, Micha{\"e}l},
TITLE = {Combining intruder theories},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {639-651},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Baudet-Cortier-Kremer/05,
AUTHOR = {Baudet, Mathieu and Cortier, V{\'e}ronique and Kremer, Steve},
TITLE = {Computationally sound implementations of equational theories against passive adversaries},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {652-663},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Abadi-Warinschi/05,
AUTHOR = {Abadi, Mart{\'{i}}n and Warinschi, Bogdan},
TITLE = {Password-based encryption analyzed},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {664-676},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Avin-Ercal/05,
AUTHOR = {Avin, Chen and Ercal, Gunes},
TITLE = {On the cover time of random geometric graphs},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {677-689},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Efthymiou-Spirakis/05,
AUTHOR = {Efthymiou, Charilaos and Spirakis, Paul G.},
TITLE = {On the existence of Hamiltonian cycles in random intersection graphs},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {690-701},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dimitrov-Plaxton/05,
AUTHOR = {Dimitrov, Nedialko B. and Plaxton, C. Greg},
TITLE = {Optimal cover time for a graph-based coupon collector process},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {702-716},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Donato-Leonardi-Tsaparas/05,
AUTHOR = {Donato, Debora and Leonardi, Stefano and Tsaparas, Panayiotis},
TITLE = {Stability and similarity of link analysis ranking algorithms},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {717-729},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pous/05,
AUTHOR = {Pous, Damien},
TITLE = {Up-to techniques for weak bisimulation},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {730-741},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_59},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Badouel-Chenou-Guillou/05,
AUTHOR = {Badouel, Eric and Chenou, Jules and Guillou, Goulven},
TITLE = {Petri algebras},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {742-754},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fokkink-Nain/05,
AUTHOR = {Fokkink, Wan and Nain, Sumit},
TITLE = {A finite basis for failure semantics},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {755-765},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_61},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Conforti-Macedonio-Sassone/05,
AUTHOR = {Conforti, Giovanni and Macedonio, Damiano and Sassone, Vladimiro},
TITLE = {Spatial logics for bigraphs},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {766-778},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_62},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fischlin/05,
AUTHOR = {Fischlin, Marc},
TITLE = {Completely non-malleable schemes},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {779-790},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_63},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Galindo/05,
AUTHOR = {Galindo, David},
TITLE = {Boneh-Franklin identity based encryption revisited},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {791-802},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_64},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gentry-Ramzan/05,
AUTHOR = {Gentry, Craig and Ramzan, Zulfikar},
TITLE = {Single-database private information retrieval with constant communication rate},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {803-815},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_65},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Di_Crescenzo-Visconti/05,
AUTHOR = {Di Crescenzo, Giovanni and Visconti, Ivan},
TITLE = {Concurrent zero knowledge in the public-key model},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {816-827},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_66},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gairing-Monien-Woclaw/05,
AUTHOR = {Gairing, Martin and Monien, Burkhard and Woclaw, Andreas},
TITLE = {A faster combinatorial approximation algorithm for scheduling unrelated parallel machines},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {828-839},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_67},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kovacs/05,
AUTHOR = {Kov{\'a}cs, Annam{\'a}ria},
TITLE = {Polynomial time preemptive sum-multicoloring on paths},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {840-852},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_68},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jain-Hajiaghayi-Talwar/05,
AUTHOR = {Jain, Kamal and Hajiaghayi, MohammadTaghi and Talwar, Kunal},
TITLE = {The generalized deadlock resolution problem},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {853-865},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_69},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Badoiu-Czumaj-Indyk-Sohler/05,
AUTHOR = {B{\v{a}}doiu, Mihai and Czumaj, Artur and Indyk, Piotr and Sohler, Christian},
TITLE = {Facility location in sublinear time},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {866-877},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_70},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chatterjee-de_Alfaro-Henzinger/05,
AUTHOR = {Chatterjee, Krishnendu and de Alfaro, Luca and Henzinger, Thomas A.},
TITLE = {The complexity of stochastic Rabin and Streett games},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {878-890},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_71},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Etessami-Yannakakis/05a,
AUTHOR = {Etessami, Kousha and Yannakakis, Mihalis},
TITLE = {Recursive Markov decision processes and recursive stochastic games},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {891-903},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_72},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Laird/05,
AUTHOR = {Laird, J.},
TITLE = {Decidability in syntactic control of interference},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {904-916},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_73},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Murawski-Ong-Walukiewicz/05,
AUTHOR = {Murawski, A.S. and Ong, C.-H.L. and Walukiewicz, I.},
TITLE = {Idealized Algol with ground recursion, and DPDA equivalence},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {917-929},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_74},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Konemann-Leonardi-Schafer-van_Zwam/05,
AUTHOR = {K{\"o}nemann, Jochen and Leonardi, Stefano and Sch{\"a}fer, Guido and van Zwam, Stefan},
TITLE = {From primal-dual to cost shares and back: A stronger $LP$ relaxation for the Steiner forest problem},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {930-942},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_75},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Borodin-Cashman-Magen/05,
AUTHOR = {Borodin, Allan and Cashman, David and Magen, Avner},
TITLE = {How well can primal-dual and local-ratio algorithms perform?},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {943-955},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_76},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hast/05,
AUTHOR = {Hast, Gustav},
TITLE = {Approximating MAX $k$CSP --- Outperforming a random assignment with almost a linear factor},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {956-968},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_77},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Patrascu-Patrascu/05,
AUTHOR = {P{\v{a}}tra{\c{s}}cu, Corina E. and P{\v{a}}tra{\c{s}}cu, Mihai},
TITLE = {On dynamic bit-probe complexity},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {969-981},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_78},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Diehl-van_Melkebeek/05,
AUTHOR = {Diehl, Scott and van Melkebeek, Dieter},
TITLE = {Time-space lower bounds for the polynomial-time hierarchy on randomized machines},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {982-993},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_79},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chattopadhyay-Hansen/05,
AUTHOR = {Chattopadhyay, Arkadev and Hansen, Kristoffer Arnsfelt},
TITLE = {Lower bounds for circuits with few modular and symmetric gates},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {994-1005},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_80},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mislove/05,
AUTHOR = {Mislove, M.W.},
TITLE = {Discrete random variables over domains},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1006-1017},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_81},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{van_Breugel-Hermida-Makkai-Worrell/05,
AUTHOR = {van Breugel, Franck and Hermida, Claudio and Makkai, Michael and Worrell, James},
TITLE = {An accessible approach to behavioural pseudometrics},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1018-1030},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_82},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Asarin-Collins/05,
AUTHOR = {Asarin, Eugene and Collins, Pieter},
TITLE = {Noisy Turing machines},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1031-1042},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_83},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Karakostas/05,
AUTHOR = {Karakostas, George},
TITLE = {A better approximation ratio for the vertex cover problem},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1043-1050},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_84},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Pal/05,
AUTHOR = {Gupta, Anupam and P{\'a}l, Martin},
TITLE = {Stochastic Steiner trees without a root},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1051-1063},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_85},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pemmaraju-Raman/05,
AUTHOR = {Pemmaraju, Sriram V. and Raman, Rajiv},
TITLE = {Approximation algorithms for the MAX-coloring problem},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1064-1075},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_86},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Grohe-Koch-Schweikardt/05,
AUTHOR = {Grohe, Martin and Koch, Christoph and Schweikardt, Nicole},
TITLE = {Tight lower bounds for query processing on streaming and external memory data},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1076-1088},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_87},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Abdulla-Deneux-Ouaknine-Worrell/05,
AUTHOR = {Abdulla, Parosh Aziz and Deneux, Johann and Ouaknine, Jo{\"e}l and Worrell, James},
TITLE = {Decidability and complexity results for timed automata via channel machines},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1089-1101},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_88},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alur-Kumar-Madhusudan-Viswanathan/05,
AUTHOR = {Alur, Rajeev and Kumar, Viraj and Madhusudan, P. and Viswanathan, Mahesh},
TITLE = {Congruences for visibly pushdown languages},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1102-1114},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_89},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elbassioni-Fishkin-Mustafa-Sitters/05,
AUTHOR = {Elbassioni, Khaled and Fishkin, Aleksei V. and Mustafa, Nabil H. and Sitters, Ren{\'e}},
TITLE = {Approximation algorithms for Euclidean group TSP},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1115-1126},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_90},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kempe-Kleinberg-Tardos/05,
AUTHOR = {Kempe, David and Kleinberg, Jon and Tardos, {\'E}va},
TITLE = {Influential nodes in a diffusion model for social networks},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1127-1138},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_91},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ambuhl/05,
AUTHOR = {Amb{\"u}hl, Christoph},
TITLE = {An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1139-1150},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_92},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Eisenbrand-Grandoni-Oriolo-Skutella/05,
AUTHOR = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin},
TITLE = {New approaches for virtual private network design},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1151-1162},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_93},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ford-Gal/05,
AUTHOR = {Ford, Jeff and G{\'a}l, Anna},
TITLE = {Hadamard tensors and lower bounds on multiparty communication complexity},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1163-1175},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_94},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beame-Pitassi-Segerlind/05,
AUTHOR = {Beame, Paul and Pitassi, Toniann and Segerlind, Nathan},
TITLE = {Lower bounds for Lov{\'a}sz-Schrijver systems and beyond follow from multiparty communication complexity},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1176-1188},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_95},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wikstrom/05,
AUTHOR = {Wikstr{\"o}m, Douglas},
TITLE = {On the $l$-ary GCD-algorithm in rings of integers},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1189-1201},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_96},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Baldamus-Parrow-Victor/05,
AUTHOR = {Baldamus, Michael and Parrow, Joachim and Victor, Bj{\"o}rn},
TITLE = {A fully abstract encoding of the $\pi$-calculus with data terms},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1202-1213},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_97},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mousavi-Reniers/05,
AUTHOR = {Mousavi, MohammadReza and Reniers, Michel A.},
TITLE = {Orthogonal extensions in structural operational semantics},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1214-1225},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_98},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{De_Nicola-Gorla-Pugliese/05,
AUTHOR = {De Nicola, Rocco and Gorla, Daniele and Pugliese, Rosario},
TITLE = {Basic observables for a calculus for global computing},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1226-1238},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_99},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Delzanno-Gabbrielli/05,
AUTHOR = {Delzanno, Giorgio and Gabbrielli, Maurizio},
TITLE = {Compositional verification of asynchronous processes via constraint solving},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1239-1250},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_100},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Farach-Colton-Landau-Sahinalp-Tsur/05,
AUTHOR = {Farach-Colton, Martin and Landau, Gad M. and Sahinalp, S. Cenk and Tsur, Dekel},
TITLE = {Optimal spaced seeds for faster approximate string matching},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1251-1262},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_101},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elias-Lagergren/05,
AUTHOR = {Elias, Isaac and Lagergren, Jens},
TITLE = {Fast neighbor joining},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1263-1274},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_102},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kao-Sanghi-Schweller/05,
AUTHOR = {Kao, Ming-Yang and Sanghi, Manan and Schweller, Robert},
TITLE = {Randomized fast design of short DNA words},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1275-1286},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_103},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Koiran-Nesme-Portier/05,
AUTHOR = {Koiran, Pascal and Nesme, Vincent and Portier, Natacha},
TITLE = {A quantum lower bound for the query complexity of Simon's problem},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1287-1298},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_104},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Spalek-Szegedy/05,
AUTHOR = {{\v{S}}palek, Robert and Szegedy, Mario},
TITLE = {All quantum adversary methods are equivalent},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1299-1311},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_105},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Magniez-Nayak/05,
AUTHOR = {Magniez, Fr{\'e}d{\'e}ric and Nayak, Ashwin},
TITLE = {Quantum complexity of testing group commutativity},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1312-1324},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_106},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dalla_Preda-Giacobazzi/05,
AUTHOR = {Dalla Preda, Mila and Giacobazzi, Roberto},
TITLE = {Semantic-based code obfuscation by abstract interpretation},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1325-1336},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_107},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Reus-Streicher/05,
AUTHOR = {Reus, Bernhard and Streicher, Thomas},
TITLE = {About Hoare logics for higher-order store},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1337-1348},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_108},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bradley-Manna-Sipma/05,
AUTHOR = {Bradley, Aaron R. and Manna, Zohar and Sipma, Henny B.},
TITLE = {The polyranking principle},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1349-1361},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_109},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Nilsson/05,
AUTHOR = {Nilsson, Bengt J.},
TITLE = {Approximate guarding of monotone and rectilinear polygons},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1362-1373},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_110},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kumar-Sabharwal-Sen/05,
AUTHOR = {Kumar, Amit and Sabharwal, Yogish and Sen, Sandeep},
TITLE = {Linear time algorithms for clustering problems in any dimensions},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1374-1385},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_111},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Berenbrink-Friedetzky-Martin/05,
AUTHOR = {Berenbrink, Petra and Friedetzky, Tom and Martin, Russell},
TITLE = {Dynamic diffusion load balancing},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1386-1398},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_112},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Radhakrishnan-Rotteler-Sen/05,
AUTHOR = {Radhakrishnan, Jaikumar and R{\"o}tteler, Martin and Sen, Pranab},
TITLE = {On the power of random bases in Fourier sampling: Hidden subgroup problem in the Heisenberg group},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1399-1411},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_113},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cary-Rudra-Sabharwal/05,
AUTHOR = {Cary, Matthew and Rudra, Atri and Sabharwal, Ashish},
TITLE = {On the hardness of embeddings between two finite metrics},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1412-1423},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_114},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wehner-de_Wolf/05,
AUTHOR = {Wehner, Stephanie and de Wolf, Ronald},
TITLE = {Improved lower bounds for locally decodable codes and private information retrieval},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1424-1436},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_115},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Atserias-Dawar-Grohe/05,
AUTHOR = {Atserias, Albert and Dawar, Anuj and Grohe, Martin},
TITLE = {Preservation under extensions on well-behaved finite structures},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1437-1449},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_116},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Knapik-Niwinski-Urzyczyn-Walukiewicz/05,
AUTHOR = {Knapik, Teodor and Niwi{\'n}ski, Damian and Urzyczyn, Pawe{\l} and Walukiewicz, Igor},
TITLE = {Unsafe grammars and panic automata},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1450-1461},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_117},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Li-Dang-Ibarra-Yen/05,
AUTHOR = {Li, Cheng and Dang, Zhe and Ibarra, Oscar H. and Yen, Hsu-Chun},
TITLE = {Signaling $P$ systems and verification problems},
BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP'2005 (Lisbon, Portugal, July 11-15, 2005)},
SERIES = {LNCS},
VOLUME = {3580},
PAGES = {1462-1473},
YEAR = {2005},
EDITOR = {Caires, Lu{\'{i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{i}}s and Palamidessi, Catuscia and Yung, Moti},
URL = {http://dx.doi.org/10.1007/11523468_118},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}