Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8--13, 2002. Proceedings (Q1613675)

The articles of this volume will be reviewed individually. The preceding colloquium (28th, 2001) has been reviewed (see Zbl 0967.00069). Indexed articles: \textit{Reif, John H.}, Molecular assembly and computation: From theory to experimental demonstrations, 1-21 [Zbl 1056.68544] \textit{Marathe, Madhav V.}, Towards a predictive computational complexity theory, 22-31 [Zbl 1056.68546] \textit{Pitts, Andrew M.}, Equivariant syntax and semantics, 32-36 [Zbl 1056.68508] \textit{Sénizergues, Géraud}, \(L(A) \)=\( L(B)\)? decidability results from complete formal systems, 37 [Zbl 1056.68548] \textit{Del Lungo, Alberto; Frosini, Andrea; Nivat, Maurice; Vuillon, Laurent}, Discrete tomography: Reconstruction under periodicity constraints, 38-56 [Zbl 1056.68592] \textit{Mannila, Heikki}, Local and global methods in data mining: Basic techniques and open problems, 57-68 [Zbl 1056.68516] \textit{Hermenegildo, M.; Puebla, G.; Bueno, F.; López-García, P.}, Program debugging and validation using semantic approximations and partial specifications, 69-72 [Zbl 1056.68509] \textit{Engebretsen, Lars; Holmerin, Jonas; Russell, Alexander}, Inapproximability results for equations over finite groups, 73-84 [Zbl 1056.68545] \textit{Pettie, Seth}, A faster all-pairs shortest path algorithm for real-weighted sparse graphs, 85-97 [Zbl 1056.68111] \textit{Colcombet, Thomas}, On families of graphs having a decidable first order theory with reachability, 98-109 [Zbl 1056.68107] \textit{Fabrikant, Alex; Koutsoupias, Elias; Papadimitriou, Christos H.}, Heuristically optimized trade-offs: A new paradigm for power laws in the internet, 110-122 [Zbl 1056.68503] \textit{Fotakis, Dimitris; Kontogiannis, Spyros; Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul}, The structure and complexity of Nash equilibria for a selfish routing game, 123-134 [Zbl 1056.68028] \textit{Khanna, Sanjeev; Naor, Joseph (Seffi); Raz, Dan}, Control message aggregation in group communication protocols, 135-146 [Zbl 1056.68506] \textit{Jurdziński, Tomasz; Lorys, Krzysztof}, Church-Rosser languages vs. UCFL., 147-158 [Zbl 1056.68095] \textit{Bala, Sebastian}, Intersection of regular languages and star hierarchy, 159-169 [Zbl 1056.68093] \textit{Lombardy, Sylvain}, On the construction of reversible automata for reversible languages, 170-182 [Zbl 1056.68097] \textit{Elmasry, Amr}, Priority queues, pairing, and adaptive sorting, 183-194 [Zbl 1056.68515] \textit{Bender, Michael A.; Cole, Richard; Raman, Rajeev}, Exponential structures for efficient cache-oblivious algorithms, 195-207 [Zbl 1056.68511] \textit{Impagliazzo, Russell; Segerlind, Nathan}, Bounded-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations (extended abstract)., 208-219 [Zbl 1056.03504] \textit{Esteban, Juan Luis; Galesi, Nicola; Messner, Jochen}, On the complexity of resolution with bounded conjunctions (extended abstract)., 220-231 [Zbl 1056.03503] \textit{Kiayias, Aggelos; Yung, Moti}, Cryptographic hardness based on the decoding of Reed-Solomon codes, 232-243 [Zbl 1062.94039] \textit{Ishai, Yuval; Kushilevitz, Eyal}, Perfect constant-round secure computation via perfect randomizing polynomials, 244-256 [Zbl 1056.68088] \textit{Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.}, Exponential lower bound for static semi-algebraic proofs, 257-268 [Zbl 1056.03037] \textit{Jakoby, Andreas; Liskiewicz, Maciej}, Paths problems in symmetric logarithmic space, 269-280 [Zbl 1056.68108] \textit{Damaschke, Peter}, Scheduling search procedures, 281-292 [Zbl 1056.68507] \textit{Iwama, Kazuo; Taketomi, Shiro}, Removable online knapsack problems, 293-305 [Zbl 1056.68588] \textit{Epstein, Leah; Seiden, Steve; van Stee, Rob}, New bounds for variable-sized and resource augmented online bin packing, 306-317 [Zbl 1056.68586] \textit{Ollinger, Nicolas}, The quest for small universal cellular automata, 318-329 [Zbl 1056.68104] \textit{Papazian, Christophe; Rémila, Eric}, Hyperbolic recognition by graph automata, 330-342 [Zbl 1056.68098] \textit{Ablayev, Farid; Moore, Cristopher; Pollett, Christopher}, Quantum and stochastic branching programs of bounded width (Track A)., 343-354 [Zbl 1056.68085] \textit{Gargano, Luisa; Hell, Pavol; Stacho, Ladislav; Vaccaro, Ugo}, Spanning trees with bounded number of branch vertices, 355-365 [Zbl 1056.68587] \textit{Beier, René; Sanders, Peter; Sivadasan, Naveen}, Energy optimal routing in radio networks using geometric data structures, 366-376 [Zbl 1056.68501] \textit{Christersson, Malin; Gasieniec, Leszek; Lingas, Andrzej}, Gossiping with bounded size messages in ad hoc radio networks (extended abstract)., 377-389 [Zbl 1056.68502] \textit{Merkle, Wolfgang}, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, 390-400 [Zbl 1056.68090] \textit{Hearn, Robert A.; Demaine, Erik D.}, The nondeterministic constraint logic model of computation: Reductions and applications, 401-413 [Zbl 1056.68086] \textit{Dalmau, Víctor}, Constraint satisfaction problems in non-deterministic logarithmic space, 414-425 [Zbl 1056.68130] \textit{Brodal, Gerth Stølting; Fagerberg, Rolf}, Cache oblivious distribution sweeping, 426-438 [Zbl 1056.68543] \textit{Östlin, Anna; Pagh, Rasmus}, One-probe search, 439-450 [Zbl 1056.68514] \textit{Charikar, Moses; Indyk, Piotr; Panigrahy, Rina}, New algorithms for subset query, partial match, orthogonal range searching, and related problems, 451-462 [Zbl 1056.68512] \textit{Martin, Keye; Mislove, Michael; Worrell, James}, Measuring the probabilistic powerdomain, 463-475 [Zbl 1056.68100] \textit{Ong, C.-H. L.; Di Gianantonio, P.}, Games characterizing Levy-Longo trees., 476-487 [Zbl 1056.68101] \textit{Bauer, Andrej; Escardó, Martín Hötzel; Simpson, Alex}, Comparing functional paradigms for exact real-number computation, 488-500 [Zbl 1056.68057] \textit{Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles}, Random sampling from Boltzmann principles (extended abstract)., 501-513 [Zbl 1056.68549] \textit{Duch, Amalia; Martínez, Conrado}, On the average performance of orthogonal range search in multidimensional data structures, 514-524 [Zbl 1056.68513] \textit{Kick, Marco}, Bialgebraic modelling of timed processes, 525-536 [Zbl 1056.68105] \textit{van Breugel, Franck; Shalit, Steven; Worrell, James}, Testing labelled Markov processes, 537-548 [Zbl 1057.68074] \textit{Hitchcock, John M.; Lutz, Jack H.}, Why computational complexity requires stricter martingales, 549-560 [Zbl 1057.68039] \textit{Hitchcock, John M.}, Correspondence principles for effective dimensions, 561-571 [Zbl 1057.68038] \textit{Meseguer, José; Rosu, Grigore}, A total approach to partial algebraic specification, 572-584 [Zbl 1057.68064] \textit{Lohrey, Markus; D'Argenio, Pedro R.; Hermanns, Holger}, Axiomatising divergence, 585-596 [Zbl 1057.68069] \textit{Cardelli, Luca; Gardner, Philippa; Ghelli, Giorgio}, A spatial logic for querying graphs, 597-610 [Zbl 1057.68606] \textit{Radzik, Tomasz}, Improving time bounds on maximum generalised flow computations by contracting the network, 611-622 [Zbl 1057.90501] \textit{Berman, Piotr; Karpinski, Marek}, Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION, 623-632 [Zbl 1057.68646] \textit{Demetrescu, Camil; Italiano, Giuseppe F.}, Improved bounds and new trade-offs for dynamic all pairs shortest paths, 633-643 [Zbl 1057.68648] \textit{Henzinger, Thomas A.; Krishnan, Sriram C.; Kupferman, Orna; Mang, Freddy Y. C.}, Synthesis of uninitialized systems, 644-656 [Zbl 1057.68060] \textit{Genest, Blaise; Muscholl, Anca; Seidl, Helmut; Zeitoun, Marc}, Infinite-state high-level MSCs: Model-checking and realizability (extended abstract), 657-668 [Zbl 1057.68625] \textit{Wich, Klaus}, Universal inherence of cycle-free context-free ambiguity functions, 669-680 [Zbl 1057.68053] \textit{Guha, Sudipto; Indyk, Piotr; Muthukrishnan, S.; Strauss, Martin J.}, Histogramming data streams with fast per-item processing, 681-692 [Zbl 1064.94515] \textit{Charikar, Moses; Chen, Kevin; Farach-Colton, Martin}, Finding frequent items in data streams, 693-703 [Zbl 1057.68600] \textit{Cachat, Thierry}, Symbolic strategy synthesis for games on pushdown graphs, 704-715 [Zbl 1057.68046] \textit{Srba, Jiří}, Strong bisimilarity and regularity of basic process algebra is PSPACE-hard, 716-727 [Zbl 1057.68071] \textit{Brodal, Gerth Stølting; Lyngsø, Rune B.; Östlin, Anna; Pedersen, Christian N. S.}, Solving the string statistics problem in time \(\mathcal{O}(n\log n)\), 728-739 [Zbl 1057.68599] \textit{Deng, Xiaotie; Li, Guojun; Li, Zimao; Ma, Bin; Wang, Lusheng}, A PTAS for distinguishing (sub)string selection, 740-751 [Zbl 1057.68134] \textit{Kuske, Dietrich; Lohrey, Markus}, On the theory of one-step rewriting in trace monoids, 752-763 [Zbl 1057.68045] \textit{Bielecki, Michał; Hidders, Jan; Paredaens, Jan; Tyszkiewicz, Jerzy; Van den Bussche, Jan}, Navigating with a browser, 764-775 [Zbl 1057.68729] \textit{Kumar, V. S. Anil; Marathe, Madhav V.}, Improved results for Stackelberg scheduling strategies, 776-787 [Zbl 1057.90018] \textit{Adamy, Udo; Ambuehl, Christoph; Anand, R. Sai; Erlebach, Thomas}, Call control in rings, 788-799 [Zbl 1057.68506] \textit{Chrobak, Marek; Epstein, Leah; Noga, John; Sgall, Jiří; van Stee, Rob; Tichý, Tomáš; Vakhania, Nodari}, Preemptive scheduling in overloaded systems, 800-811 [Zbl 1057.68542] \textit{Karhumäki, J.; Lisovik, L. P.}, The equivalence problem of finite substitutions on \(ab^*c \), with applications, 812-820 [Zbl 1057.68048] \textit{Stirling, Colin}, Deciding DPDA equivalence is primitive recursive, 821-832 [Zbl 1057.68052] \textit{Bojańczyk, Mikołaj}, Two-way alternating automata and finite models, 833-844 [Zbl 1057.03029] \textit{Berman, Piotr; Karpinski, Marek; Nekrich, Yakov}, Approximating Huffman codes in parallel, 845-855 [Zbl 1057.68743] \textit{Fantozzi, Carlo; Pietracaprina, Andrea; Pucci, Geppino}, Seamless integration of parallelism and memory hierarchy (extended abstract), 856-867 [Zbl 1057.68617] \textit{Nisan, Noam}, The communication complexity of approximate set packing and covering, 868-875 [Zbl 1057.68645] \textit{Doerr, Benjamin}, Antirandomizing the wrong game, 876-887 [Zbl 1059.91013] \textit{Akcoglu, Karhan; Drineas, Petros; Kao, Ming-Yang}, Fast universalization of investment strategies with provably good relative returns, 888-900 [Zbl 1057.91038] \textit{Adler, Micah; Räcke, Harald; Sivadasan, Naveen; Sohler, Christian; Vöcking, Berthold}, Randomized pursuit-evasion in graphs, 901-912 [Zbl 1057.91015] \textit{Wells, J. B.}, The essence of principal typings, 913-925 [Zbl 1057.03023] \textit{Adsul, Bharat; Sohoni, Milind}, Complete and tractable local linear time temporal logics over traces, 926-937 [Zbl 1057.68055] \textit{Gastin, Paul; Mukund, Madhavan}, An elementary expressively complete temporal logic for Mazurkiewicz traces, 938-949 [Zbl 1057.68058] \textit{Brattka, Vasco}, Random numbers and an incomplete immune recursive set, 950-961 [Zbl 1057.03052] \textit{Hertling, Peter}, A Banach-Mazur computable but not Markov computable function on the computable real numbers, 962-972 [Zbl 1057.03054] \textit{Czumaj, Artur; Lingas, Andrzej; Zhao, Hairong}, Polynomial-time approximation schemes for the Euclidean survivable network design problem, 973-984 [Zbl 1057.90053] \textit{Björklund, Andreas; Husfeldt, Thore}, Finding a path of superlogarithmic length, 985-992 [Zbl 1057.68647] \textit{Uehara, Ryuhei}, Linear time algorithms on chordal bipartite and strongly chordal graphs, 993-1004 [Zbl 1057.68654] \textit{Holmerin, Jonas}, Improved inapproximability results for vertex cover on \(k\)-uniform hypergraphs, 1005-1016 [Zbl 1057.68079] \textit{Kohayakawa, Yoshiharu; Nagle, Brendan; Rödl, Vojtěch}, Efficient testing of hypergraphs (extended abstract), 1017-1028 [Zbl 1057.68649] \textit{Wu, Xiaodong; Chen, Danny Z.}, Optimal net surface problems with applications, 1029-1042 [Zbl 1057.68723] \textit{Bonichon, Nicolas; Le Saëc, Bertrand; Mosbah, Mohamed}, Wagner's theorem on realizers, 1043-1053 [Zbl 1058.05057] \textit{Liberatore, Vincenzo}, Circular arrangements, 1054-1065 [Zbl 1057.68009]