Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11--15, 2005. Proceedings. (Q2577427)

The articles of this volume will be reviewed individually. The preceding colloquium has been reviewed (see Zbl 1056.68007). Indexed articles: \textit{Valiant, Leslie G.}, Holographic circuits, 1-15 [Zbl 1081.68022] \textit{Datta, Anupam; Derek, Ante; Mitchell, John C.; Shmatikov, Vitaly; Turuani, Mathieu}, Probabilistic polynomial-time semantics for a protocol security logic, 16-29 [Zbl 1082.68571] \textit{Castagna, Giuseppe; Frisch, Alain}, A gentle introduction to semantic subtyping, 30-34 [Zbl 1082.68581] \textit{Libkin, Leonid}, Logics for unranked trees: An overview, 35-50 [Zbl 1084.68028] \textit{Gairing, Martin; Lücking, Thomas; Monien, Burkhard; Tiemann, Karsten}, Nash equilibria, the price of anarchy and the fully mixed Nash equilibrium conjecture, 51-65 [Zbl 1084.91006] \textit{Bille, Philip; Gørtz, Inge}, The tree inclusion problem: In optimal space and faster, 66-77 [Zbl 1085.68566] \textit{Alstrup, Stephen; Gørtz, Inge Li; Rauhe, Theis; Thorup, Mikkel; Zwick, Uri}, Union-find with constant time deletions, 78-89 [Zbl 1084.68026] \textit{Franceschini, Gianni; Grossi, Roberto}, Optimal in-place sorting of vectors and records, 90-102 [Zbl 1085.68033] \textit{Kaligosi, Kanela; Mehlhorn, Kurt; Munro, J. Ian; Sanders, Peter}, Towards optimal multiple selection, 103-114 [Zbl 1085.68030] \textit{Zimand, Marius}, Simple extractors via constructions of cryptographic pseudo-random generators, 115-127 [Zbl 1081.94037] \textit{Horvitz, Omer; Katz, Jonathan}, Bounds on the efficiency of ``black-box'' commitment schemes, 128-139 [Zbl 1081.94028] \textit{Wee, Hoeteck}, On round-efficient argument systems, 140-152 [Zbl 1082.68574] \textit{Tamassia, Roberto; Triandopoulos, Nikos}, Computational bounds on hierarchical data processing with applications to information security, 153-165 [Zbl 1082.68573] \textit{Dietzfelbinger, Martin; Weidling, Christoph}, Balanced allocation and dictionaries with tightly packed constant size bins, 166-178 [Zbl 1082.68557] \textit{Chiniforooshan, Ehsan; Farzan, Arash; Mirzazadeh, Mehdi}, Worst case optimal union-intersection expression evaluation, 179-190 [Zbl 1082.68556] \textit{Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter}, Measure and conquer: Domination -- a case study, 191-203 [Zbl 1082.68866] \textit{Kursawe, Klaus; Shoup, Victor}, Optimistic asynchronous atomic broadcast, 204-215 [Zbl 1082.68519] \textit{Di Crescenzo, Giovanni; Kiayias, Aggelos}, Asynchronous perfectly secure communication over one-time pads, 216-227 [Zbl 1082.68518] \textit{Persiano, Giuseppe; Visconti, Ivan}, Single-prover concurrent zero knowledge in almost constant rounds, 228-240 [Zbl 1082.68572] \textit{Kowaluk, Miroslaw; Lingas, Andrzej}, LCA queries in directed acyclic graphs, 241-248 [Zbl 1082.68593] \textit{Roditty, Liam; Zwick, Uri}, Replacement paths and \(k\) simple shortest paths in unweighted directed graphs, 249-260 [Zbl 1082.68594] \textit{Roditty, Liam; Thorup, Mikkel; Zwick, Uri}, Deterministic constructions of approximate distance oracles and spanners, 261-272 [Zbl 1082.68087] \textit{Kavitha, Telikepalli}, An \(\tilde O( m^{2} n )\) randomized algorithm to compute a minimum cycle basis of a directed graph, 273-284 [Zbl 1082.68084] \textit{Moran, Tal; Naor, Moni}, Basing cryptographic protocols on tamper-evident seals, 285-297 [Zbl 1082.94527] \textit{Catalano, Dario; Visconti, Ivan}, Hybrid trapdoor commitments and their applications, 298-310 [Zbl 1082.94012] \textit{Hopper, Nicholas}, On steganographic chosen covertext security, 311-323 [Zbl 1082.94521] \textit{Braeken, An; Borissov, Yuri; Nikova, Svetla; Preneel, Bart}, Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties, 324-334 [Zbl 1082.94011] \textit{Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David}, Label-guided graph exploration by a finite automaton, 335-346 [Zbl 1082.68588] \textit{Chlebus, Bogdan S.; Gąsieniec, Leszek; Kowalski, Dariusz R.; Radzik, Tomasz}, On the wake-up problem in radio networks, 347-359 [Zbl 1082.68504] \textit{Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan}, Distance constrained labelings of graphs of bounded treewidth, 360-372 [Zbl 1082.68080] \textit{Gu, Qian-Ping; Tamaki, Hisao}, Optimal branch-decomposition of planar graphs in \(O ( n^{3})\) time, 373-384 [Zbl 1082.68591] \textit{Hromkovič, Juraj; Schnitger, Georg}, NFAs with and without \(\epsilon\)-transitions, 385-396 [Zbl 1082.68052] \textit{Béal, Marie-Pierre; Lombardy, Sylvain; Sakarovitch, Jacques}, On the equivalence of \(\mathbb{Z}\)-automata., 397-409 [Zbl 1082.68069] \textit{Czeizler, Eugen; Kari, Jarkko}, A tight linear bound on the neighborhood of inverse cellular automata, 410-420 [Zbl 1082.68072] \textit{Beaudry, Martin; Lemieux, François; Thérien, Denis}, Groupoids that recognize only regular languages, 421-433 [Zbl 1082.68582] \textit{Kiltz, Eike; Mityagin, Anton; Panjwani, Saurabh; Raghavan, Barath}, Append-only signatures, 434-445 [Zbl 1082.94541] \textit{Trolin, Mårten; Wikström, Douglas}, Hierarchical group signatures, 446-458 [Zbl 1082.94546] \textit{Lipmaa, Helger; Wang, Guilin; Bao, Feng}, Designated verifier signature schemes: Attacks, new security notions and a new construction, 459-471 [Zbl 1082.94542] \textit{Maurer, Ueli; Sjödin, Johan}, Single-key AIL-MACs from any FIL-MAC, 472-484 [Zbl 1082.94543] \textit{Zhang, Li}, The efficiency and fairness of a fixed budget resource allocation game, 485-496 [Zbl 1084.91025] \textit{Lin, Henry; Roughgarden, Tim; Tardos, Éva; Walkover, Asher}, Braess's paradox, Fibonacci numbers, and exponential inapproximability, 497-512 [Zbl 1084.90044] \textit{Droste, Manfred; Gastin, Paul}, Weighted automata and weighted logics, 513-525 [Zbl 1084.03036] \textit{Tesson, Pascal; Thérien, Denis}, Restricted two-variable FO+MOD sentences, circuits and communication complexity, 526-538 [Zbl 1084.03037] \textit{Haneda, Mitsuhiro; Kawazoe, Mitsuru; Takahashi, Tetsuya}, Suitable curves for genus-4 HCC over prime fields: Point counting formulae for hyperelliptic curves of type \(y^{2}= x^{2 k +1}+ ax\), 539-550 [Zbl 1084.94016] \textit{Kayal, Neeraj}, Solvability of a system of bivariate polynomial equations over a finite field (extended abstract), 551-562 [Zbl 1084.11509] \textit{Jampala, Hema; Zeh, Norbert}, Cache-oblivious planar shortest paths, 563-575 [Zbl 1085.68604] \textit{Brodal, Gerth Stølting; Fagerberg, Rolf; Moruz, Gabriel}, Cache-aware and cache-oblivious adaptive sorting, 576-588 [Zbl 1085.68574] \textit{Wegener, Ingo}, Simulated annealing beats Metropolis in combinatorial optimization, 589-601 [Zbl 1084.68123] \textit{Epstein, Leah; Levy, Meital}, Online interval coloring and variants, 602-613 [Zbl 1085.68603] \textit{Chan, Wun-Tat; Lam, Tak-Wah; Wong, Prudence W. H.}, Dynamic bin packing of unit fractions items, 614-626 [Zbl 1085.68741] \textit{Englert, Matthias; Westermann, Matthias}, Reordering buffer management for non-uniform cost models, 627-638 [Zbl 1085.68742] \textit{Chevalier, Yannick; Rusinowitch, Michaël}, Combining intruder theories, 639-651 [Zbl 1084.94512] \textit{Baudet, Mathieu; Cortier, Véronique; Kremer, Steve}, Computationally sound implementations of equational theories against passive adversaries, 652-663 [Zbl 1084.94510] \textit{Abadi, Martín; Warinschi, Bogdan}, Password-based encryption analyzed, 664-676 [Zbl 1084.94509] \textit{Avin, Chen; Ercal, Gunes}, On the cover time of random geometric graphs, 677-689 [Zbl 1084.05504] \textit{Efthymiou, Charilaos; Spirakis, Paul G.}, On the existence of Hamiltonian cycles in random intersection graphs, 690-701 [Zbl 1084.05063] \textit{Dimitrov, Nedialko B.; Plaxton, C. Greg}, Optimal cover time for a graph-based coupon collector process, 702-716 [Zbl 1084.05503] \textit{Donato, Debora; Leonardi, Stefano; Tsaparas, Panayiotis}, Stability and similarity of link analysis ranking algorithms, 717-729 [Zbl 1085.68602] \textit{Pous, Damien}, Up-to techniques for weak bisimulation, 730-741 [Zbl 1084.68085] \textit{Badouel, Eric; Chenou, Jules; Guillou, Goulven}, Petri algebras, 742-754 [Zbl 1084.68080] \textit{Fokkink, Wan; Nain, Sumit}, A finite basis for failure semantics, 755-765 [Zbl 1084.68082] \textit{Conforti, Giovanni; Macedonio, Damiano; Sassone, Vladimiro}, Spatial logics for bigraphs, 766-778 [Zbl 1084.68081] \textit{Fischlin, Marc}, Completely non-malleable schemes (extended abstract), 779-790 [Zbl 1084.94515] \textit{Galindo, David}, Boneh-Franklin identity based encryption revisited, 791-802 [Zbl 1084.94015] \textit{Gentry, Craig; Ramzan, Zulfikar}, Single-database private information retrieval with constant communication rate, 803-815 [Zbl 1084.68043] \textit{Di Crescenzo, Giovanni; Visconti, Ivan}, Concurrent zero knowledge in the public-key model, 816-827 [Zbl 1084.94513] \textit{Gairing, Martin; Monien, Burkhard; Woclaw, Andreas}, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, 828-839 [Zbl 1085.68535] \textit{Kovács, Annamária}, Polynomial time preemptive sum-multicoloring on paths, 840-852 [Zbl 1084.90024] \textit{Jain, Kamal; Hajiaghayi, MohammadTaghi; Talwar, Kunal}, The generalized deadlock resolution problem, 853-865 [Zbl 1085.68582] \textit{Bădoiu, Mihai; Czumaj, Artur; Indyk, Piotr; Sohler, Christian}, Facility location in sublinear time, 866-877 [Zbl 1084.90027] \textit{Chatterjee, Krishnendu; de Alfaro, Luca; Henzinger, Thomas A.}, The complexity of stochastic Rabin and Streett games, 878-890 [Zbl 1085.68060] \textit{Etessami, Kousha; Yannakakis, Mihalis}, Recursive Markov decision processes and recursive stochastic games, 891-903 [Zbl 1085.68089] \textit{Laird, J.}, Decidability in syntactic control of interference, 904-916 [Zbl 1085.68091] \textit{Murawski, A. S.; Ong, C.-H. L.; Walukiewicz, I.}, Idealized Algol with ground recursion, and DPDA equivalence, 917-929 [Zbl 1085.68092] \textit{Könemann, Jochen; Leonardi, Stefano; Schäfer, Guido; van Zwam, Stefan}, From primal-dual to cost shares and back: A stronger LP relaxation for the Steiner forest problem, 930-942 [Zbl 1084.90525] \textit{Borodin, Allan; Cashman, David; Magen, Avner}, How well can primal-dual and local-ratio algorithms perform?, 943-955 [Zbl 1084.90524] \textit{Hast, Gustav}, Approximating MAX \(k\)CSP -- outperforming a random assignment with almost a linear factor, 956-968 [Zbl 1085.68185] \textit{Ptraşcu, Corina E.; Ptraşcu, Mihai}, On dynamic bit-probe complexity, 969-981 [Zbl 1085.68032] \textit{Diehl, Scott; van Melkebeek, Dieter}, Time-space lower bounds for the polynomial-time hierarchy on randomized machines, 982-993 [Zbl 1085.68062] \textit{Chattopadhyay, Arkadev; Hansen, Kristoffer Arnsfelt}, Lower bounds for circuits with few modular and symmetric gates, 994-1005 [Zbl 1085.68061] \textit{Mislove, M. W.}, Discrete random variables over domains, 1006-1017 [Zbl 1085.68084] \textit{van Breugel, Franck; Hermida, Claudio; Makkai, Michael; Worrell, James}, An accessible approach to behavioural pseudometrics, 1018-1030 [Zbl 1085.68101] \textit{Asarin, Eugene; Collins, Pieter}, Noisy Turing machines, 1031-1042 [Zbl 1085.68042] \textit{Karakostas, George}, A better approximation ratio for the vertex cover problem, 1043-1050 [Zbl 1085.68112] \textit{Gupta, Anupam; Pál, Martin}, Stochastic Steiner trees without a root, 1051-1063 [Zbl 1084.90034] \textit{Pemmaraju, Sriram V.; Raman, Rajiv}, Approximation algorithms for the max-coloring problem, 1064-1075 [Zbl 1085.68114] \textit{Grohe, Martin; Koch, Christoph; Schweikardt, Nicole}, Tight lower bounds for query processing on streaming and external memory data, 1076-1088 [Zbl 1085.68036] \textit{Abdulla, Parosh Aziz; Deneux, Johann; Ouaknine, Joël; Worrell, James}, Decidability and complexity results for timed automata via channel machines, 1089-1101 [Zbl 1085.68078] \textit{Alur, Rajeev; Kumar, Viraj; Madhusudan, P.; Viswanathan, Mahesh}, Congruences for visibly pushdown languages, 1102-1114 [Zbl 1085.68079] \textit{Elbassioni, Khaled; Fishkin, Aleksei V.; Mustafa, Nabil H.; Sitters, René}, Approximation algorithms for Euclidean group TSP, 1115-1126 [Zbl 1084.90043] \textit{Kempe, David; Kleinberg, Jon; Tardos, Éva}, Influential nodes in a diffusion model for social networks, 1127-1138 [Zbl 1084.91053] \textit{Ambühl, Christoph}, An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks, 1139-1150 [Zbl 1085.68501] \textit{Eisenbrand, Friedrich; Grandoni, Fabrizio; Oriolo, Gianpaolo; Skutella, Martin}, New approaches for virtual private network design, 1151-1162 [Zbl 1085.68005] \textit{Ford, Jeff; Gál, Anna}, Hadamard tensors and lower bounds on multiparty communication complexity, 1163-1175 [Zbl 1085.68054] \textit{Beame, Paul; Pitassi, Toniann; Segerlind, Nathan}, Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity, 1176-1188 [Zbl 1085.68053] \textit{Wikström, Douglas}, On the \(l\)-ary GCD-algorithm in rings of integers, 1189-1201 [Zbl 1084.11068] \textit{Baldamus, Michael; Parrow, Joachim; Victor, Björn}, A fully abstract encoding of the \(\pi\)-calculus with data terms (extended abstract), 1202-1213 [Zbl 1085.68594] \textit{Mousavi, Mohammad Reza; Reniers, Michel A.}, Orthogonal extensions in structural operational semantics (extended abstract), 1214-1225 [Zbl 1085.68593] \textit{De Nicola, Rocco; Gorla, Daniele; Pugliese, Rosario}, Basic observables for a calculus for global computing, 1226-1238 [Zbl 1085.68098] \textit{Delzanno, Giorgio; Gabbrielli, Maurizio}, Compositional verification of asynchronous processes via constraint solving, 1239-1250 [Zbl 1081.68646] \textit{Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel}, Optimal spaced seeds for faster approximate string matching, 1251-1262 [Zbl 1081.68674] \textit{Elias, Isaac; Lagergren, Jens}, Fast neighbor joining, 1263-1274 [Zbl 1081.92030] \textit{Kao, Ming-Yang; Sanghi, Manan; Schweller, Robert}, Randomized fast design of short DNA words, 1275-1286 [Zbl 1081.68660] \textit{Koiran, Pascal; Nesme, Vincent; Portier, Natacha}, A quantum lower bound for the query complexity of Simon's problem, 1287-1298 [Zbl 1081.68027] \textit{Špalek, Robert; Szegedy, Mario}, All quantum adversary methods are equivalent, 1299-1311 [Zbl 1081.68025] \textit{Magniez, Frédéric; Nayak, Ashwin}, Quantum complexity of testing group commutativity, 1312-1324 [Zbl 1081.68033] \textit{Dalla Preda, Mila; Giacobazzi, Roberto}, Semantic-based code obfuscation by abstract interpretation, 1325-1336 [Zbl 1081.68576] \textit{Reus, Bernhard; Streicher, Thomas}, About Hoare logics for higher-order store, 1337-1348 [Zbl 1081.68577] \textit{Bradley, Aaron R.; Manna, Zohar; Sipma, Henny B.}, The polyranking principle, 1349-1361 [Zbl 1081.68568] \textit{Nilsson, Bengt J.}, Approximate guarding of monotone and rectilinear polygons, 1362-1373 [Zbl 1081.68729] \textit{Kumar, Amit; Sabharwal, Yogish; Sen, Sandeep}, Linear time algorithms for clustering problems in any dimensions, 1374-1385 [Zbl 1081.68746] \textit{Berenbrink, Petra; Friedetzky, Tom; Martin, Russell}, Dynamic diffusion load balancing, 1386-1398 [Zbl 1081.68548] \textit{Radhakrishnan, Jaikumar; Rötteler, Martin; Sen, Pranab}, On the power of random bases in Fourier sampling: Hidden subgroup problem in the Heisenberg group, 1399-1411 [Zbl 1084.81022] \textit{Cary, Matthew; Rudra, Atri; Sabharwal, Ashish}, On the hardness of embeddings between two finite metrics, 1412-1423 [Zbl 1081.68597] \textit{Wehner, Stephanie; de Wolf, Ronald}, Improved lower bounds for locally decodable codes and private information retrieval, 1424-1436 [Zbl 1081.68028] \textit{Atserias, Albert; Dawar, Anuj; Grohe, Martin}, Preservation under extensions on well-behaved finite structures, 1437-1449 [Zbl 1081.03025] \textit{Knapik, Teodor; Niwiński, Damian; Urzyczyn, Paweł; Walukiewicz, Igor}, Unsafe grammars and panic automata, 1450-1461 [Zbl 1081.68054] \textit{Li, Cheng; Dang, Zhe; Ibarra, Oscar H.; Yen, Hsu-Chun}, Signaling P systems and verification problems, 1462-1473 [Zbl 1081.68021]