Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12--16, 2004. Proceedings. (Q1763052)

The articles of this volume will be reviewed individually. The preceding colloquium has been reviewed (see Zbl 1029.00041). Indexed articles: \textit{Harper, Robert}, Self-adjusting computation, 1-2 [Zbl 1098.68951] \textit{Henzinger, Monika}, The past, present, and future of web search engines, 3 [Zbl 1098.68520] \textit{Hofmann, Martin}, What do program logics and type systems have in common?, 4-7 [Zbl 1098.68548] \textit{Razborov, Alexander A.}, Feasible proofs and computations: Partnership and fusion, 8-14 [Zbl 1099.03512] \textit{Rytter, Wojciech}, Grammar compression, LZ-encodings, and string algorithms with implicit input, 15-27 [Zbl 1099.68028] \textit{Yannakakis, Mihalis}, Testing, optimizaton, and games, 28-45 [Zbl 1099.68662] \textit{Abadi, Martín; Cortier, Véronique}, Deciding knowledge in security protocols under equational theories, 46-58 [Zbl 1099.94026] \textit{Abbott, Michael; Altenkirch, Thorsten; Ghani, Neil}, Representing nested inductive types using W-types, 59-71 [Zbl 1099.03058] \textit{Aggarwal, Gagan; Feder, Tomás; Motwani, Rajeev; Zhu, An}, Algorithms for multi-product pricing, 72-83 [Zbl 1099.91512] \textit{Alekhnovich, Michael; Hirsch, Edward A.; Itsykson, Dmitry}, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas, 84-96 [Zbl 1098.68052] \textit{de Alfaro, Luca; Faella, Marco; Stoelinga, Mariëlle}, Linear and branching metrics for quantitative transition systems, 97-109 [Zbl 1098.68092] \textit{Alon, Noga; Asodi, Vera}, Learning a hidden subgraph, 110-121 [Zbl 1098.68629] \textit{Alur, Rajeev; Bernadsky, Mikhail; Madhusudan, P.}, Optimal reachability for weighted timed games, 122-133 [Zbl 1098.68061] \textit{Andrews, Matthew; Zhang, Lisa}, Wavelength assignment in optical networks with fixed fiber capacity, 134-145 [Zbl 1098.68008] \textit{Arge, Lars; Meyer, Ulrich; Toma, Laura}, External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs, 146-157 [Zbl 1098.68630] \textit{Atkey, Robert}, A \(\lambda\)-calculus for resource separation, 158-170 [Zbl 1098.68023] \textit{Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe}, The power of verification for one-parameter agents, 171-182 [Zbl 1098.90056] \textit{Awerbuch, Baruch; Scheideler, Christian}, Group spreading: A protocol for provably secure distributed name service, 183-195 [Zbl 1098.68515] \textit{Bansal, Nikhil; Fleischer, Lisa K.; Kimbrel, Tracy; Mahdian, Mohammad; Schieber, Baruch; Sviridenko, Maxim}, Further improvements in competitive guarantees for QoS buffering, 196-207 [Zbl 1098.68516] \textit{Berger, N.; Borgs, C.; Chayes, J. T.; D'Souza, R. M.; Kleinberg, R. D.}, Competition-induced preferential attachment, 208-221 [Zbl 1098.68009] \textit{Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev}, Approximating longest directed paths and cycles, 222-233 [Zbl 1098.68094] \textit{Blundo, Carlo; D'Arco, Paolo; De Santis, Alfredo}, Definitions and bounds for self-healing key distribution schemes, 234-245 [Zbl 1098.68517] \textit{Bojańczyk, Mikołaj; Colcombet, Thomas}, Tree-walking automata cannot be determinized, 246-256 [Zbl 1098.68620] \textit{Boudes, Pierre}, Projecting games on hypercoherences, 257-268 [Zbl 1098.68022] \textit{Bournez, Olivier; Hainry, Emmanuel}, An analog characterization of elementarily computable functions over the real numbers, 269-280 [Zbl 1098.03047] \textit{Bruns, Glenn; Godefroid, Patrice}, Model checking with multi-valued logics, 281-293 [Zbl 1098.68079] \textit{Bulatov, Andrei; Grohe, Martin}, The complexity of partition functions, 294-306 [Zbl 1098.68616] \textit{Busi, Nadia; Gabbrielli, Maurizio; Zavattaro, Gianluigi}, Comparing recursion, replication, and iteration in process calculi, 307-319 [Zbl 1098.68086] \textit{Chen, Ning; Deng, Xiaotie; Sun, Xiaoming; Yao, Andrew Chi-Chih}, Dynamic price sequence and incentive compatibility (extended abstract), 320-331 [Zbl 1098.91524] \textit{Cheney, James}, The complexity of equivariant unification, 332-344 [Zbl 1098.03023] \textit{Christodoulou, George; Koutsoupias, Elias; Nanavati, Akash}, Coordination mechanisms, 345-357 [Zbl 1098.91079] \textit{Chrobak, Marek; Jawor, Wojciech; Sgall, Jiří; Tichý, Tomáš}, Online scheduling of equal-length jobs: Randomization and restarts help, 358-370 [Zbl 1098.68538] \textit{Codenotti, Bruno; Varadarajan, Kasturi}, Efficient computation of equilibrium prices for markets with Leontief utilities, 371-382 [Zbl 1098.91086] \textit{Coja-Oghlan, Amin}, Coloring semirandom graphs optimally, 383-395 [Zbl 1098.05073] \textit{Czumaj, Artur; Sohler, Christian}, Sublinear-time approximation for clustering via random sampling, 396-407 [Zbl 1098.68113] \textit{Dąbrowski, Robert; Plandowski, Wojtek}, Solving two-variable word equations (extended abstract), 408-419 [Zbl 1098.68633] \textit{Dawar, Anuj; Grädel, Erich; Kreutzer, Stephan}, Backtracking games and inflationary fixed points, 420-432 [Zbl 1098.68622] \textit{Deng, Xiaotie; Li, Guojun}, A PTAS for embedding hypergraph in a cycle (extended abstract), 433-444 [Zbl 1098.05504] \textit{Deng, Yuxin; Sangiorgi, Davide}, Towards an algebraic theory of typed mobile processes, 445-456 [Zbl 1099.68668] \textit{Durand, Bruno; Muchnik, Andrei; Ushakov, Maxim; Vereshchagin, Nikolai}, Ecological Turing machines, 457-468 [Zbl 1099.68029] \textit{Dvořák, Zdeněk; Král', Daniel; Pangrác, Ondřej}, Locally consistent constraint satisfaction problems (extended abstract), 469-480 [Zbl 1099.68739] \textit{Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi}, Quantum query complexity of some graph problems, 481-493 [Zbl 1099.68640] \textit{Edalat, A.; Pattinson, D.}, A domain theoretic account of Picard's theorem, 494-505 [Zbl 1098.65078] \textit{Faggian, Claudia}, Interactive observability in Ludics, 506-518 [Zbl 1099.03509] \textit{Feige, Uriel; Ofek, Eran}, Easily refutable subformulas of large random 3CNF formulas, 519-530 [Zbl 1099.68641] \textit{Feigenbaum, Joan; Kannan, Sampath; McGregor, Andrew; Suri, Siddharth; Zhang, Jian}, On graph problems in a semi-streaming model, 531-543 [Zbl 1099.68679] \textit{Fleischer, Lisa}, Linear tolls suffice: new bounds and algorithms for tolls in single source networks, 544-554 [Zbl 1099.90516] \textit{Flum, Jörg; Grohe, Martin; Weyer, Mark}, Bounded fixed-parameter tractability and \(\log^{2} n\) nondeterministic bits, 555-567 [Zbl 1099.68642] \textit{Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan}, Exact (exponential) algorithms for treewidth and minimum fill-in, 568-580 [Zbl 1099.68076] \textit{Fomin, Fedor V.; Thilikos, Dimitrios M.}, Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up, 581-592 [Zbl 1099.68077] \textit{Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul}, Selfish unsplittable flows, 593-605 [Zbl 1099.90512] \textit{Franceschini, Gianni; Grossi, Roberto}, A general technique for managing strings in comparison-driven data structures, 606-617 [Zbl 1099.68600] \textit{Frisch, Alain; Cardelli, Luca}, Greedy regular expression matching, 618-629 [Zbl 1099.68769] \textit{Fu, Bin; Wang, Wei}, A \(2^{O(n^{1-{1\over d}}\log n)}\) time algorithm for \(d\)-dimensional protein folding in the HP-model, 630-644 [Zbl 1099.68130] \textit{Gairing, Martin; Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard; Rode, Manuel}, Nash equilibria in discrete routing games with convex latency functions, 645-657 [Zbl 1100.91003] \textit{Gandhi, Rajiv; Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas}, Improved results for data migration and open shop scheduling, 658-669 [Zbl 1099.68015] \textit{Gąsieniec, Leszek; Kranakis, Evangelos; Pelc, Andrzej; Xin, Qin}, Deterministic M2M multicast in radio networks (extended abstract), 670-682 [Zbl 1099.68510] \textit{Ghica, D. R.; Murawski, A. S.; Ong, C.-H. L.}, Syntactic control of concurrency, 683-694 [Zbl 1099.68656] \textit{Guruswami, Venkatesan; Indyk, Piotr}, Linear-time list decoding in error-free settings (extended abstract), 695-707 [Zbl 1099.94522] \textit{Haghverdi, Esfandiar; Scott, Philip}, A categorical model for the geometry of interaction, 708-720 [Zbl 1099.03514] \textit{Halevy, Shirley; Kushilevitz, Eyal}, Testing monotonicity over graph products, 721-732 [Zbl 1099.68681] \textit{Halperin, Eran; Karp, Richard M.}, The minimum-entropy set cover problem, 733-744 [Zbl 1099.94519] \textit{Harsha, Prahladh; Ishai, Yuval; Kilian, Joe; Nissim, Kobbi; Venkatesh, S.}, Communication versus computation, 745-756 [Zbl 1099.68636] \textit{Heeringa, Brent; Adler, Micah}, Optimal website design with the constrained subtree selection problem, 757-769 [Zbl 1099.68682] \textit{Hoory, Shlomo; Magen, Avner; Myers, Steven; Rackoff, Charles}, Simple permutations mix well, 770-781 [Zbl 1099.68678] \textit{Indyk, Piotr; Lewenstein, Moshe; Lipsky, Ohad; Porat, Ely}, Closest pair problems in very high dimensions, 782-792 [Zbl 1099.68123] \textit{Jeandel, Emmanuel}, Universality in quantum computation, 793-804 [Zbl 1099.68030] \textit{Jothi, Raja; Raghavachari, Balaji}, Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design, 805-818 [Zbl 1099.68079] \textit{Kalyanasundaram, Bala; Velauthapillai, Mahe}, Fairness to all while downsizing, 819-830 [Zbl 1099.90019] \textit{Katsumata, Shin-ya}, A generalisation of pre-logical predicates to simply typed formal systems, 831-845 [Zbl 1099.03012] \textit{Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna}, A faster algorithm for minimum cycle basis of graphs, 846-857 [Zbl 1103.05086] \textit{Krauthgamer, Robert; Lee, James R.}, The black-box complexity of nearest neighbor search, 858-869 [Zbl 1099.68604] \textit{Kunc, Michal}, Regular solutions of language inequalities and well quasi-orders, 870-881 [Zbl 1099.68664] \textit{Laird, J.}, A calculus of coroutines, 882-893 [Zbl 1099.68548] \textit{Lebhar, Emmanuelle; Schabanel, Nicolas}, Almost optimal decentralized routing in long-range contact networks, 894-905 [Zbl 1099.68513] \textit{Lohrey, Markus}, Word problems on compressed words, 906-918 [Zbl 1099.68646] \textit{Lyngsø, Rune B.}, Complexity of pseudoknot prediction in simple models, 919-931 [Zbl 1099.68037] \textit{Magniez, Frédéric; de Rougemont, Michel}, Property testing of regular tree languages, 932-944 [Zbl 1099.68647] \textit{Martin, Keye}, Entropy as a fixed point, 945-958 [Zbl 1099.68644] \textit{Meer, K.}, Transparent long proofs: A first PCP theorem for NP\(_{\mathbb R}\), 959-970 [Zbl 1099.68637] \textit{van Melkebeek, Dieter; Raz, Ran}, A time lower bound for satisfiability, 971-982 [Zbl 1099.68638] \textit{Merkle, Wolfgang; Mihailović, Nenad; Slaman, Theodore A.}, Some results on effective randomness, 983-995 [Zbl 1099.03033] \textit{Midrijānis, Gatis}, A polynomial quantum query lower bound for the set equality problem, 996-1005 [Zbl 1099.68038] \textit{Munro, J. Ian; Rao, S. Srinivasa}, Succinct representations of functions, 1006-1015 [Zbl 1099.68603] \textit{Müller-Olm, Markus; Seidl, Helmut}, A note on Karr's algorithm, 1016-1028 [Zbl 1099.68022] \textit{Nikoletseas, S.; Raptopoulos, C.; Spirakis, P.}, The existence and efficient construction of large independent sets in general random intersection graphs, 1029-1040 [Zbl 1103.05083] \textit{Ostrovsky, Rafail; Rackoff, Charles; Smith, Adam}, Efficient consistency proofs for generalized queries on a committed database, 1041-1053 [Zbl 1099.68622] \textit{Paluch, Katarzyna}, A \(2 \frac{1}{8}\)-approximation algorithm for rectangle tiling, 1054-1065 [Zbl 1099.68772] \textit{Roşu, Grigore}, Extensional theories and rewriting, 1066-1079 [Zbl 1099.03021] \textit{Sahinalp, S. Cenk; Utis, Andrey}, Hardness of string similarity search and other indexing problems, 1080-1098 [Zbl 1099.68039] \textit{Samer, Marko; Veith, Helmut}, A syntactic characterization of distributive LTL queries, 1099-1110 [Zbl 1099.68058] \textit{Sanders, Peter; Sivadasan, Naveen; Skutella, Martin}, Online scheduling with bounded migration, 1111-1122 [Zbl 1099.68773] \textit{Schweikardt, Nicole}, On the expressive power of monadic least fixed point logic, 1123-1135 [Zbl 1099.68639] \textit{Seidl, Helmut; Schwentick, Thomas; Muscholl, Anca; Habermehl, Peter}, Counting in trees for free, 1136-1149 [Zbl 1099.03010] \textit{Serre, Olivier}, Games with winning conditions of high Borel complexity, 1150-1162 [Zbl 1099.03510] \textit{Skelley, Alan}, Propositional PSPACE reasoning with Boolean programs versus quantified Boolean formulas, 1163-1175 [Zbl 1099.03049] \textit{Soltys, Michael}, LA, permutations, and the Hajós calculus, 1176-1187 [Zbl 1099.03513] \textit{Toftdal, Michael}, A calibration of ineffective theorems of analysis in a hierarchy of semi-classical logical principles (extended abstract), 1188-1200 [Zbl 1099.03515] \textit{Vassilvitskii, Sergei; Yannakakis, Mihalis}, Efficiently computing succinct trade-off curves, 1201-1213 [Zbl 1099.90577] \textit{Völzer, Hagen}, On randomization versus synchronization in distributed systems, 1214-1226 [Zbl 1098.68090] \textit{Williams, Ryan}, A new algorithm for optimal constraint satisfaction and its implications, 1227-1237 [Zbl 1098.68120] \textit{Zhang, Shengyu}, On the power of Ambainis's lower bounds, 1238-1250 [Zbl 1098.68053]