Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 -- July 4, 2003. Proceedings (Q1419516)

The articles of this volume will be reviewed individually. The preceding colloquiuum has been reviewed (see Zbl 0993.00041). Indexed articles: \textit{Bergstra, Jan A.; Bethke, Inge}, Polarized process algebra and program equivalence, 1-21 [Zbl 1039.68040] \textit{Condon, Anne}, Problems on RNA secondary structure prediction and design, 22-32 [Zbl 1060.68634] \textit{Fiat, Amos}, Some issues regarding search, censorship, and anonymity in peer to peer networks, 33 [Zbl 1039.68512] \textit{Mutzel, Petra}, The SPQR-tree data structure in graph drawing, 34-46 [Zbl 1039.68547] \textit{Peled, Doron}, Model checking and testing combined, 47-63 [Zbl 1039.68075] \textit{Vardi, Moshe Y.}, Logic and automata: A match made in heaven, 64-65 [Zbl 1039.03508] \textit{Hromkovič, Juraj; Schnitger, Georg}, Pushdown automata and multicounter machines, a comparison of computation modes, 66-80 [Zbl 1039.68554] \textit{De Bonis, Annalisa; Gasieniec, Leszek; Vaccaro, Ugo}, Generalized framework for selectors with applications in optimal group testing, 81-96 [Zbl 1039.68116] \textit{Bleichenbacher, Daniel; Kiayias, Aggelos; Yung, Moti}, Decoding of interleaved Reed Solomon codes over noisy data, 97-108 [Zbl 1042.94529] \textit{Blom, Stefan; Fokkink, Wan; Nain, Sumit}, On the axiomatizability of ready traces, ready simulation, and failure traces, 109-118 [Zbl 1039.68081] \textit{Gorla, Daniele; Pugliese, Rosario}, Resource access and mobility control with dynamic privileges acquisition, 119-132 [Zbl 1039.68542] \textit{Busi, Nadia; Gabbrielli, Maurizio; Zavattaro, Gianluigi}, Replication vs. recursive definitions in channel based calculi, 133-144 [Zbl 1039.68082] \textit{Ageev, Alexander; Ye, Yinyu; Zhang, Jiawei}, Improved combinatorial approximation algorithms for the \(k\)-level facility location problem, 145-156 [Zbl 1060.90677] \textit{Bläser, Markus}, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, 157-163 [Zbl 1060.90694] \textit{Gandhi, Rajiv; Halperin, Eran; Khuller, Samir; Kortsarz, Guy; Srinivasan, Aravind}, An improved approximation algorithm for vertex cover with hard capacities (extended abstract), 164-175 [Zbl 1060.68694] \textit{Arora, Sanjeev; Chang, Kevin L.}, Approximation schemes for degree-restricted MST and red-blue separation problem, 176-188 [Zbl 1039.68165] \textit{Chekuri, Chandra; Guha, Sudipto; Naor, Joseph}, Approximating Steiner \(k\)-cuts, 189-199 [Zbl 1039.68166] \textit{Coja-Oghlan, Amin; Moore, Cristopher; Sanwalani, Vishal}, MAX \(k\)-CUT and approximating the chromatic number of random graphs, 200-211 [Zbl 1039.68167] \textit{Elkin, Michael; Kortsarz, Guy}, Approximation algorithm for directed telephone multicast problem, 212-223 [Zbl 1039.68511] \textit{Ancona, Davide; Fagorzi, Sonia; Moggi, Eugenio; Zucca, Elena}, Mixin modules and computational effects, 224-238 [Zbl 1039.68541] \textit{Okhotin, Alexander}, Decision problems for language equations with Boolean operations, 239-251 [Zbl 1039.68069] \textit{Bruni, Roberto; Meseguer, José}, Generalized rewrite theories, 252-266 [Zbl 1039.03020] \textit{Antunes, Luís; Fortnow, Lance}, Sophistication revisited, 267-277 [Zbl 1039.68058] \textit{Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira}, Scaled dimension and nonuniform complexity, 278-290 [Zbl 1039.68052] \textit{Høyer, Peter; Mosca, Michele; de Wolf, Ronald}, Quantum search on bounded-error inputs, 291-299 [Zbl 1039.68056] \textit{Jain, Rahul; Radhakrishnan, Jaikumar; Sen, Pranab}, A direct sum theorem in communication complexity via message compression, 300-315 [Zbl 1039.68048] \textit{Franceschini, Gianni; Grossi, Roberto}, Optimal cache-oblivious implicit dictionaries, 316-331 [Zbl 1039.68041] \textit{Gál, Anna; Miltersen, Peter Bro}, The cell probe complexity of succinct data structures, 332-344 [Zbl 1039.68544] \textit{Munro, J. Ian; Raman, Rajeev; Raman, Venkatesh; Rao, Satti Srinivasa}, Succinct representations of permutations, 345-356 [Zbl 1039.68546] \textit{Raman, Rajeev; Rao, Satti Srinivasa}, Succinct dynamic dictionaries and trees, 357-368 [Zbl 1039.68043] \textit{Korman, Amos; Peleg, David}, Labeling schemes for weighted dynamic trees, 369-383 [Zbl 1039.68513] \textit{Baswana, Surender; Sen, Sandeep}, A simple linear time algorithm for computing a \((2k-1)\)-spanner of \(O(n^{1+1/k})\) size in weighted graphs, 384-396 [Zbl 1039.05056] \textit{Hall, Alex; Hippler, Steffen; Skutella, Martin}, Multicommodity flows over time: Efficient algorithms and complexity, 397-409 [Zbl 1060.90512] \textit{Chekuri, Chandra; Mydlarz, Marcelo; Shepherd, F. Bruce}, Multicommodity demand flow in a tree, 410-425 [Zbl 1060.90511] \textit{Droste, Manfred; Kuske, Dietrich}, Skew and infinitary formal power series, 426-438 [Zbl 1039.68065] \textit{Hromkovič, Juraj; Schnitger, Georg}, Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser's separation, 439-451 [Zbl 1039.68068] \textit{Denis, François; Esposito, Yann}, Residual languages and probabilistic automata, 452-463 [Zbl 1039.68064] \textit{Stoelinga, Mariëlle; Vaandrager, Frits}, A testing scenario for probabilistic automata, 464-477 [Zbl 1039.68071] \textit{Sénizergues, Géraud}, The equivalence problem for \(t\)-turn DPDA is co-NP, 478-489 [Zbl 1039.68070] \textit{Holzer, Markus; Kutrib, Martin}, Flip-pushdown automata: \(k+1\) pushdown reversals are better than \(k\), 490-501 [Zbl 1039.68066] \textit{Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay}, Convergence time to Nash equilibria, 502-513 [Zbl 1039.68017] \textit{Feldmann, Rainer; Gairing, Martin; Lücking, Thomas; Monien, Burkhard; Rode, Manuel}, Nashification and the coordination ratio for a selfish routing game, 514-526 [Zbl 1060.68531] \textit{Bansal, Vipul; Agrawal, Aseem; Malhotra, Varun S.}, Stable marriages with multiple partners: Efficient search for an optimal solution, 527-542 [Zbl 1060.91514] \textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid; Makino, Kazuhisa}, An intersection inequality for discrete distributions and related generation problems, 543-555 [Zbl 1060.90691] \textit{Cachat, Thierry}, Higher order pushdown automata, the Caucal hierarchy of graphs and parity games, 556-569 [Zbl 1039.68063] \textit{Mayr, Richard}, Undecidability of weak bisimulation equivalence for 1-counter processes, 570-583 [Zbl 1039.68084] \textit{Merro, Massimo; Nardelli, Francesco Zappa}, Bisimulation proof methods for mobile ambients, 584-598 [Zbl 1039.68085] \textit{Carayol, Arnaud; Colcombet, Thomas}, On equivalent representations of infinite structures, 599-610 [Zbl 1039.03021] \textit{Schönhage, Arnold}, Adaptive raising strategies optimizing relative efficiency, 611-623 [Zbl 1039.68123] \textit{Sitters, René A.; Stougie, Leen; de Paepe, Willem E.}, A competitive algorithm for the general 2-server problem, 624-636 [Zbl 1039.68124] \textit{Fotakis, Dimitris}, On the competitive ratio for online facility location, 637-652 [Zbl 1039.68117] \textit{Albers, Susanne; van Stee, Rob}, A study of integrated document and connection caching, 653-667 [Zbl 1039.68509] \textit{Xie, Gaoyan; Dang, Zhe; Ibarra, Oscar H.}, A solvable class of quadratic Diophantine equations with applications to verification of infinite-state systems, 668-680 [Zbl 1039.68077] \textit{Klaedtke, Felix; Rueß, Harald}, Monadic second-order logics with cardinalities, 681-696 [Zbl 1039.03004] \textit{Kupferman, Orna; Vardi, Moshe Y.}, \(\Pi_2 \cap \Sigma_2 \equiv \text{AFMC}\), 697-713 [Zbl 1039.03023] \textit{Rybina, Tatiana; Voronkov, Andrei}, Upper bounds for a theory of queues, 714-724 [Zbl 1039.03005] \textit{Berger, Noam; Bollobás, Béla; Borgs, Christian; Chayes, Jennifer; Riordan, Oliver}, Degree distribution of the FKP network model, 725-738 [Zbl 1039.68510] \textit{Blondel, Vincent D.; Van Dooren, Paul}, Similarity matrices for pairs of graphs, 739-750 [Zbl 1039.68089] \textit{Bhatia, Randeep; Chuzhoy, Julia; Freund, Ari; Naor, Joseph}, Algorithmic aspects of bandwidth trading, 751-766 [Zbl 1039.68535] \textit{Johannsen, Jan; Lange, Martin}, CTL\(^{+}\) is complete for double exponential time, 767-775 [Zbl 1039.68073] \textit{La Torre, Salvatore; Napoli, Margherita; Parente, Mimmo; Parlato, Gennaro}, Hierarchical and recursive state machines with context-dependent properties, 776-789 [Zbl 1039.68074] \textit{Schnoebelen, Philippe}, Oracle circuits for branching-time model checking, 790-801 [Zbl 1039.68076] \textit{Gargano, Luisa; Hammar, Mikael}, There are spanning spiders in dense graphs (and we know how to find them), 802-816 [Zbl 1039.68095] \textit{Fiala, Jiří; Paulusma, Daniël}, The computational complexity of the role assignment problem, 817-828 [Zbl 1039.68094] \textit{Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.}, Fixed-parameter algorithms for the \((k,r)\)-center in planar graphs and map graphs, 829-844 [Zbl 1039.68093] \textit{Chen, Jianer; Kanj, Iyad A.; Perković, Ljubomir; Sedgwick, Eric; Xia, Ge}, Genus characterizes the complexity of graph problems: Some tight results, 845-856 [Zbl 1039.68092] \textit{Eisner, Cindy; Fisman, Dana; Havlicek, John; McIsaac, Anthony; Van Campenhout, David}, The definition of a temporal clock operator, 857-870 [Zbl 1039.03505] \textit{Ariola, Zena M.; Herbelin, Hugo}, Minimal classical logic and control operators, 871-885 [Zbl 1039.03019] \textit{Henzinger, Thomas A.; Jhala, Ranjit; Majumdar, Rupak}, Counterexample-guided control, 886-902 [Zbl 1039.68555] \textit{Hannay, Jo}, Axiomatic criteria for quotients and subobjects for higher-order data types, 903-917 [Zbl 1039.68079] \textit{Matias, Yossi; Porat, Ely}, Efficient pebbling for list traversal synopses, 918-928 [Zbl 1039.68545] \textit{Amir, Amihood; Aumann, Yonatan; Cole, Richard; Lewenstein, Moshe; Porat, Ely}, Function matching: Algorithms, applications, and a lower bound, 929-942 [Zbl 1039.68933] \textit{Kärkkäinen, Juha; Sanders, Peter}, Simple linear work suffix array construction, 943-955 [Zbl 1039.68042] \textit{Gutiérrez, Francisco; Ruiz, Blas}, Expansion postponement via cut elimination in sequent calculi for pure type systems, 956-968 [Zbl 1039.03045] \textit{Bugliesi, Michele; Crafa, Silvia; Prelic, Amela; Sassone, Vladimiro}, Secrecy in untrusted networks, 969-983 [Zbl 1039.68516] \textit{Chattopadhyay, Arkadev; Thérien, Denis}, Locally commutative categories, 984-995 [Zbl 1041.18005] \textit{Doberkat, Ernst-Erich}, Semi-pullbacks and bisimulations in categories of stochastic relations, 996-1007 [Zbl 1041.18006] \textit{Rabinovich, Alexander}, Quantitative analysis of probabilistic lossy channel systems, 1008-1021 [Zbl 1039.68557] \textit{de Alfaro, Luca; Henzinger, Thomas A.; Majumdar, Rupak}, Discounting the future in systems theory, 1022-1037 [Zbl 1039.68087] \textit{de Alfaro, Luca; Faella, Marco}, Information flow in concurrent games, 1038-1053 [Zbl 1039.68086] \textit{Ikeda, Satoshi; Kubo, Izumi; Okumoto, Norihiro; Yamashita, Masafumi}, Impact of local topological information on random walks on finite graphs, 1054-1067 [Zbl 1040.60037] \textit{Jägersküpper, Jens}, Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces, 1068-1079 [Zbl 1039.68586] \textit{Poulalhon, Dominique; Schaeffer, Gilles}, Optimal coding and sampling of triangulations, 1080-1094 [Zbl 1039.05028] \textit{Bodirsky, Manuel; Gröpl, Clemens; Kang, Mihyun}, Generating labeled planar graphs uniformly at random, 1095-1107 [Zbl 1039.05057] \textit{Crescenzi, Pilu; Gambosi, Giorgio; Nicosia, Gaia; Penna, Paolo; Unger, Walter}, Online load balancing made simple: Greedy strikes back, 1108-1122 [Zbl 1039.68536] \textit{Naor, Joseph; Shachnai, Hadas; Tamir, Tami}, Real-time scheduling with a budget, 1123-1137 [Zbl 1039.68018] \textit{Dean, Brian C.; Goemans, Michel X.}, Improved approximation algorithms for minimum-space advertisement scheduling, 1138-1152 [Zbl 1039.68537] \textit{Awerbuch, Baruch; Brinkmann, André; Scheideler, Christian}, Anycasting in adversarial systems: Routing and admission control, 1153-1168 [Zbl 1039.68534] \textit{Bespamyatnikh, Sergei; Segal, Michael}, Dynamic algorithms for approximating interdistances, 1169-1180 [Zbl 1039.68768] \textit{Cieliebak, Mark; Flocchini, Paola; Prencipe, Giuseppe; Santoro, Nicola}, Solving the robots gathering problem, 1181-1196 [Zbl 1039.68129]