Automata, languages and programming. 28th international colloquium, ICALP 2001, Crete, Greece, July 8--12, 2001. Proceedings (Q5941726)

The articles of mathematical interest will be reviewed individually. The preceding colloquium (27th, 2000) has been reviewed (see Zbl 0941.00034). Indexed articles: \textit{Papadimitriou, Christos H.}, Algorithms, games, and the internet (extended abstract), 1-3 [Zbl 0986.68566] \textit{Trakhtenbrot, Boris A.}, Automata, circuits, and hybrids: Facets of continuous time, 4-23 [Zbl 0986.68029] \textit{Bouajjani, Ahmed}, Languages, rewriting systems, and verification of infinite-state systems, 24-39 [Zbl 0986.68517] \textit{Große-Rhode, Martin}, Integrating semantics for object-oriented system models, 40-60 [Zbl 0986.68505] \textit{Nielsen, Mogens}, Modelling with partial orders -- why and why not? Extended abstract, 61-63 [Zbl 0986.68709] \textit{Wegener, Ingo}, Theoretical aspects of evolutionary algorithms, 64-78 [Zbl 0986.68137] \textit{Bläser, Markus}, Improvements of the Alder-Strassen bound: Algebras with nonzero radical, 79-91 [Zbl 0986.68037] \textit{Boros, E.; Elbassioni, K.; Gurvich, V.; Khachiyan, L.; Makino, K.}, On generating all minimal integer solutions for a monotone system of linear inequalities, 92-103 [Zbl 0986.90024] \textit{Hesse, William}, Division is in uniform \({\text \texttt{TC}}^0\), 104-114 [Zbl 0986.68041] \textit{Agarwal, Pankaj K.; Arge, Lars; Procopiuc, Octavian; Vitter, Jeffrey Scott}, A framework for index bulk loading and dynamization, 115-127 [Zbl 0986.68020] \textit{Bilardi, Gianfranco; Peserico, Enoch}, A characterization of temporal locality and its portability across memory hierarchies, 128-139 [Zbl 0987.68514] \textit{Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian N. S.; Östlin, Anna}, The complexity of constructing evolutionary trees using experiments, 140-151 [Zbl 0986.68100] \textit{Flajolet, Philippe; Guivarc'h, Yves; Szpankowski, Wojciech; Vallée, Brigitte}, Hidden pattern statistics, 152-165 [Zbl 0986.68136] \textit{Sadakane, Kunihiko; Takki-Chebihi, Nadia; Tokuyama, Takeshi}, Combinatorics and algorithms on low-discrepancy roundings of a real sequence, 166-177 [Zbl 0986.65051] \textit{Tiskin, Alexandre}, All-pairs shortest paths computation in the BSP model, 178-189 [Zbl 0986.68953] \textit{Chazelle, Bernard; Rubinfeld, Ronitt; Trevisan, Luca}, Approximating the minimum spanning tree weight in sublinear time, 190-200 [Zbl 0987.68527] \textit{Engebretsen, Lars; Karpinski, Marek}, Approximation hardness of TSP with bounded metrics, 201-212 [Zbl 0986.90082] \textit{Feige, Uriel; Langberg, Michael}, The \(\text{RPR}^2\) rounding technique for semidefinite programs, 213-224 [Zbl 0986.90041] \textit{Gandhi, Rajiv; Khuller, Samir; Srinivasan, Aravind}, Approximation algorithms for partial covering problems. Extended abstract, 225-236 [Zbl 0986.90502] \textit{Seiden, Steven S.}, On the online bin packing problem, 237-248 [Zbl 0987.68039] \textit{Thorup, Mikkel}, Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs, 249-260 [Zbl 0986.90067] \textit{Alber, Jochen; Fernau, Henning; Niedermeier, Rolf}, Parameterized complexity: Exponential speed-up for planar graph problems, 261-272 [Zbl 0987.68040] \textit{Cai, Liming; Juedes, David}, Subexponential parameterized algorithms collapse the W-hierarchy, 273-284 [Zbl 0986.68038] \textit{Chakrabarti, Amit; Khot, Subhash}, Improved lower bounds on the randomized complexity of graph properties, 285-296 [Zbl 0986.68036] \textit{Dodis, Yevgeniy}, New imperfect random source with applications to coin-flipping, 297-309 [Zbl 0986.68168] \textit{Friedman, Joel; Goerdt, Andreas}, Recognizing more unsatisfiable random 3-SAT instances efficiently, 310-321 [Zbl 0986.68042] \textit{Fürer, Martin}, Weisfeiler-Lehman refinement requires at least a linear number of iterations, 322-333 [Zbl 0986.68039] \textit{Goldreich, Oded; Vadhan, Salil; Wigderson, Avi}, On interactive proofs with a laconic prover (extended abstract), 334-345 [Zbl 0986.68533] \textit{Høyer, Peter; Neerbek, Jan; Shi, Yaoyun}, Quantum complexities of ordered searching, sorting, and element distinctness, 346-357 [Zbl 0987.68041] \textit{Sen, Pranab; Venkatesh, S.}, Lower bounds in the quantum cell probe model, 358-369 [Zbl 0986.68022] \textit{Bandini, Emanuele; Segala, Roberto}, Axiomatizations for probabilistic bisimulation, 370-381 [Zbl 0986.68073] \textit{Boudol, Gérard; Castellani, Ilaria}, Noninterference for concurrent programs, 382-395 [Zbl 0986.68012] \textit{Madhusudan, P.; Thiagarajan, P. S.}, Distributed controller synthesis for local specifications, 396-407 [Zbl 0986.68079] \textit{Sangiorgi, Davide; Valente, Andrea}, A distributed abstract machine for safe ambients (extended abstract), 408-420 [Zbl 0986.68511] \textit{van Breugel, Franck; Worrell, James}, Towards quantitative verification of probabilistic transition systems, 421-432 [Zbl 0986.68093] \textit{Li, Zhangjian; Nakano, Shin-ichi}, Efficient generation of plane triangulations without repetitions, 433-443 [Zbl 0986.68951] \textit{Lin, Guo-Hui; Chen, Zhi-Zhong; Jiang, Tao; Wen, Jianjun}, The longest common subsequence problem for sequences with nested arc annotations (extended abstract), 444-455 [Zbl 0986.68532] \textit{Park, Sang-Min; Lee, Jae-Ha; Chwa, Kyung-Yong}, Visibility-based pursuit-evasion in a polygonal region by a searcher, 456-468 [Zbl 0986.68158] \textit{Roura, Salvador}, A new method for balancing binary search trees, 469-480 [Zbl 0986.68021] \textit{Cormode, Graham; Muthukrishnan, S.; Ṣahinalp, Süleyman Cenk}, Permutation editing and matching via embeddings, 481-492 [Zbl 0986.92501] \textit{Czumaj, Artur; Sohler, Christian}, Testing hypergraph coloring, 493-505 [Zbl 0986.05047] \textit{Isobe, Shuji; Zhou, Xiao; Nishizeki, Takao}, Total colorings of degenerated graphs, 506-517 [Zbl 0986.05048] \textit{Margara, Luciano; Simon, Janos}, Decidable properties of graphs of all-optical networks, 518-529 [Zbl 0986.90007] \textit{Mustafa, Nabil H.; Pekeč, Aleksandar}, Majority consensus and the local majority rule, 530-542 [Zbl 0986.68099] \textit{Diekert, Volker; Muscholl, Anca}, Solvability of equations in free partially commutative groups is decidable, 543-554 [Zbl 0986.20036] \textit{Droste, Manfred; Zhang, Guo-Qiang}, Rational transformations of formal power series, 555-566 [Zbl 0986.68069] \textit{Ferenczi, Sébastien; Holton, Charles; Zamboni, Luca Q.}, Combinatorics of three-interval exchanges, 567-578 [Zbl 0986.68102] \textit{Harju, Tero; Ibarra, Oscar; Karhumäki, Juhani; Salomaa, Arto}, Decision questions concerning semilinearity, morphisms, and commutation of languages, 579-590 [Zbl 0986.68048] \textit{Kirsten, Daniel}, The star problem in trace monoids: Reductions beyond C4 (extended abstract), 591-602 [Zbl 0986.68523] \textit{Kunc, Michal}, The trace coding problem is undecidable. (Extended abstract), 603-614 [Zbl 0987.68051] \textit{Rivals, Eric; Rahmann, Sven}, Combinatorics of periods in strings, 615-626 [Zbl 0986.68101] \textit{Shankar, Priti; Kumar, P. N. A.; Singh, Harmeet; Rajan, B. S.}, Minimal tail-biting trellises for certain cyclic block codes are easy to construct, 627-638 [Zbl 0986.94037] \textit{Aziz Abdulla, Parosh; Boasson, Luc; Bouajjani, Ahmed}, Effective lossy queue languages, 639-651 [Zbl 0986.68044] \textit{Benedikt, Michael; Godefroid, Patrice; Reps, Thomas}, Model checking of unrestricted hierarchical state machines, 652-666 [Zbl 0986.68506] \textit{Boreale, Michele}, Symbolic trace analysis of cryptographic protocols, 667-681 [Zbl 0986.94022] \textit{Comon, Hubert; Cortier, Véronique; Mitchell, John}, Tree automata with one memory, set constraints, and ping-pong protocols, 682-693 [Zbl 0986.68047] \textit{Etessami, Kousha; Wilke, Thomas; Schuller, Rebecca A.}, Fair simulation relations, parity games, and state space reduction for Büchi automata, 694-707 [Zbl 0986.68049] \textit{Gottlob, Georg; Pichler, Reinhard}, Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width, 708-719 [Zbl 0987.68046] \textit{Muscholl, Anca; Peled, Doron}, From finite state communication protocols to high-level message sequence charts, 720-731 [Zbl 0986.68060] \textit{Caragiannis, Ioannis; Ferreira, Afonso; Kaklamanis, Christos; Pérennes, Stéphane; Rivano, Hervé}, Fractional path coloring with applications to WDM networks, 732-743 [Zbl 0986.05046] \textit{Cohen, Edith; Halperin, Eran; Kaplan, Haim}, Performance aspects of distributed caches using TTL-based consistency, 744-756 [Zbl 0986.68541] \textit{Fraigniaud, Pierre; Gavoille, Cyril}, Routing in trees, 757-772 [Zbl 0987.68001] \textit{Havill, Jessen T.}, Online packet routing on linear arrays and rings, 773-784 [Zbl 0986.68502] \textit{Sibeyn, Jop F.}, Faster gossiping on butterflies, 785-796 [Zbl 0987.68501] \textit{Alur, Rajeev; Etessami, Kousha; Yannakakis, Mihalis}, Realizability and verification of MSC graphs, 797-808 [Zbl 0986.68518] \textit{Madhusudan, P.}, Reasoning about sequential and branching behaviours of message sequence graphs, 809-820 [Zbl 0986.68061] \textit{Maier, Patrick}, A set-theoretic framework for assume-guarantee reasoning, 821-834 [Zbl 0986.68057] \textit{Viswanathan, Mahesh; Viswanathan, Ramesh}, Foundations for circular compositional reasoning, 835-847 [Zbl 0986.68059] \textit{Chekuri, Chandra; Khanna, Sanjeev}, A PTAS for minimizing weighted completion time on uniformly related machines (extended abstract), 848-861 [Zbl 0986.68503] \textit{Chrobak, Marek; Csirik, János; Imreh, Csanád; Noga, John; Sgall, Jiří}, The buffer minimization problem for multiprocessor scheduling with conflicts, 862-874 [Zbl 0986.68006] \textit{Fishkin, Aleksei V.; Jansen, Klaus; Porkolab, Lorant}, On minimizing average weighted completion time of multiprocessor tasks with release dates, 875-886 [Zbl 0986.68007] \textit{Woeginger, Gerhard J.}, On the approximability of average completion time scheduling under precedence constraints, 887-897 [Zbl 0986.68008] \textit{Baum-Waidner, Birgit}, Optimistic asynchronous multi-party contract signing with reduced number of rounds, 898-911 [Zbl 0986.94506] \textit{Beimel, Amos; Ishai, Yuval}, Information-theoretic private information retrieval: A unified construction (extended abstract), 912-926 [Zbl 0986.68509] \textit{Feigenbaum, Joan; Ishai, Yuval; Malkin, Tal; Nissim, Kobbi; Strauss, Martin J.}, Secure multiparty computation of approximations (extended abstract), 927-938 [Zbl 0986.68954] \textit{Kiayias, Aggelos; Yung, Moti}, Secure games with polynomial expressions, 939-950 [Zbl 0986.68508] \textit{Bofill, Miquel; Godoy, Guillem}, On the completeness of arbitrary selection strategies for paramodulation, 951-962 [Zbl 0986.68122] \textit{Honsell, Furio; Miculan, Marino; Scagnetto, Ivan}, An axiomatic approach to metareasoning on nominal algebras in HOAS, 963-978 [Zbl 0986.68016] \textit{Korovin, Konstantin; Voronkov, Andrei}, Knuth-Bendix constraint solving is NP-complete, 979-992 [Zbl 0986.68045] \textit{Schröder, Lutz; Mossakowski, Till; Tarlecki, Andrzej}, Amalgamation in CASL via enriched signatures, 993-1004 [Zbl 0986.68015] \textit{Atserias, Albert; Bonet, María Luisa; Esteban, Juan Luis}, Lower bounds for the weak pigeonhole principle beyond resolution, 1005-1016 [Zbl 0986.03046] \textit{Buhrman, Harry; Tromp, John; Vitányi, Paul}, Time and space bounds for reversible simulation (extended abstract), 1017-1027 [Zbl 0986.68512] \textit{Dai, Jack J.; Lathrop, James I.; Lutz, Jack H.; Mayordomo, Elvira}, Finite-state dimension, 1028-1039 [Zbl 0986.68035] \textit{Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W.}, The complexity of computing the size of an interval, 1040-1051 [Zbl 0986.68043] \textit{Jurdziński, Tomasz; Kutyłowski, Mirosław}, Communication gap for finite memory devices, 1052-1064 [Zbl 0986.68034] \textit{Servedio, Rocco A.}, Separating quantum and classical earning, 1065-1080 [Zbl 0986.68030]