Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9--15, 2000. Proceedings (Q1572745)

The articles of mathematical interest will be reviewed individually. The preceding colloquium (26th, 1999) has been indicated (see Zbl 0917.00014). Indexed articles: \textit{Engebretsen, Lars; Holmerin, Jonas}, Clique is hard to approximate within \(n^{1-o(1)}\), 2-12 [Zbl 0973.68079] \textit{Krivelevich, Michael; Vu, Van H.}, Approximating the independence number and the chromatic number in expected polynomial time, 13-24 [Zbl 0973.68183] \textit{Calcagno, Cristiano; Moggi, Eugenio; Taha, Walid}, Closed types as a simple approach to save imperative multi-stage programming, 25-36 [Zbl 0973.68037] \textit{Mycroft, Alan; Sharp, Richard}, A statistically allocated parallel functional language, 37-48 [Zbl 0973.68586] \textit{Pettie, Seth; Ramachandran, Vijaya}, An optimal minimum spanning tree algorithm, 49-60 [Zbl 0973.68534] \textit{Hagerup, Torben}, Improved shortest paths on the word RAM, 61-72 [Zbl 0973.68535] \textit{Alstrup, Stephen; Holm, Jacob}, Improved algorithms for finding level ancestors in dynamic trees, 73-84 [Zbl 0973.68665] \textit{Plotkin, Gordon; Power, John; Sannella, Donald; Tennent, Robert}, Lax logical relations, 85-102 [Zbl 0973.03016] \textit{Ghica, Dan R.; McCusker, Guy}, Reasoning about Idealized Algol using regular languages, 103-115 [Zbl 0973.68506] \textit{Martin, Keye}, The measurement process in domain theory, 116-126 [Zbl 0973.68131] \textit{Engels, Gregor; Heckel, Reiko}, Graph transformation as a conceptual and formal framework for system modeling and model evolution, 127-150 [Zbl 0973.68626] \textit{Atserias, Albert; Galesi, Nicola; Gavaldà, Ricard}, Monotone proofs of the pigeon hole principle, 151-162 [Zbl 0973.03074] \textit{Lüttgen, Gerald; Mendler, Michael}, Fully-abstract statecharts semantics via intuitionistic Kripke models, 163-174 [Zbl 0973.68130] \textit{Bruni, Roberto; Sassone, Vladimiro}, Algebraic models for contextual nets, 175-186 [Zbl 0973.68161] \textit{Bollig, Beate; Wegener, Ingo}, Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, 187-198 [Zbl 0973.68515] \textit{Hromkovič, Juray; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg; Seibert, Sebastian}, Measures of nondeterminism in finite automata, 199-210 [Zbl 0973.68114] \textit{Diekert, Volker; Gastin, Paul}, LTL is expressively complete for Mazurkiewicz traces, 211-222 [Zbl 0973.68165] \textit{Moszkowski, Ben C.}, An automata-theoretic completeness proof for interval temporal logic. (Extended abstract), 223-234 [Zbl 0973.03508] \textit{Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Schöning, Uwe}, Deterministic algorithms for \(k\)-SAT based on covering codes and local search, 236-247 [Zbl 0973.68253] \textit{Blömer, Johannes}, Closest vectors, successive minima, and dual HKZ-bases of lattices, 248-259 [Zbl 0973.11103] \textit{Libkin, Leonid}, Variable independence, quantifier elimination, and constraint representations, 260-271 [Zbl 0973.68083] \textit{Bulatov, Andrei A.; Krokhin, Andrei A.; Jeavons, Peter}, Constraint satisfaction problems and finite algebras, 272-282 [Zbl 0973.68181] \textit{Seiden, Steven S.}, An optimal online algorithm for bounded space variable-sized bin packing, 283-295 [Zbl 0973.68527] \textit{Csirik, János; Woeginger, Gerhard J.}, Resource augmentation for online bounded space bin packing. (Extended abstract), 296-304 [Zbl 0973.68529] \textit{Ambühl, Christoph; Gärtner, Bernd; von Stengel, Bernhard}, Optimal projective algorithms for the list update problem, 305-316 [Zbl 0973.68514] \textit{Kučera, Antonín}, Efficient verification algorithms for one-counter processes, 317-328 [Zbl 0973.68163] \textit{Mayr, Richard}, On the complexity of bisimulation problems for basic parallel processes, 329-341 [Zbl 0973.68166] \textit{Lugiez, Denis; Schnoebelen, Philippe}, Decidable first-order transition logics for PA-processes, 342-353 [Zbl 0973.68162] \textit{Focardi, Riccardo; Gorrieri, Roberto; Martinelli, Fabio}, Non interference for the analysis of cryptographic protocols, 354-372 [Zbl 0973.94517] \textit{Akhavi, Ali; Vallée, Brigitte}, Average bit-complexity of Euclidean algorithms, 373-387 [Zbl 0973.11102] \textit{Banderier, Cyril; Flajolet, Philippe; Schaeffer, Gilles; Soria, Michèle}, Planar maps and Airy phenomena, 388-402 [Zbl 0973.05067] \textit{König, Barbara}, Analysing input/output-capabilities of mobile processes with a generic type system, 403-414 [Zbl 0973.68144] \textit{Hennessy, Matthew; Riely, James}, Information flow vs. resource access in the asynchronous pi-calculus. (Extended abstract), 415-427 [Zbl 0973.68519] \textit{Manna, Zohar; Sipma, Henny B.}, Alternating the temporal picture for safety, 429-450 [Zbl 0973.68141] \textit{De Santis, Alfredo; Di Crescenzo, Giovanni; Persiano, Giuseppe}, Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all NP relations. (Extended abstract), 451-462 [Zbl 0973.94526] \textit{Aiello, William; Bhatt, Sandeep; Ostrovsky, Refail; Rajagopalan, S. Raj.}, Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP, 463-474 [Zbl 0973.68523] \textit{Esparza, Javier; Heljanko, Keijo}, A new unfolding approach to LTL model checking, 475-486 [Zbl 0973.68140] \textit{Meenakshi, B.; Ramanujam, R.}, Reasoning about message passing in finite state environments, 487-498 [Zbl 0973.68167] \textit{Baudron, Olivier; Pointcheval, David; Stern, Jacques}, Extended notions of security for multicast public key cryptosystems, 499-511 [Zbl 0973.94530] \textit{Cachin, Christian; Camenisch, Jan; Kilian, Joe; Müller, Joy}, One-round secure computation and secure autonomous mobile agents. (Extended abstract), 512-523 [Zbl 0973.94545] \textit{Baum-Waidner, Birgit; Waidner, Michael}, Round-optimal and abuse-free optimistic multi-party contract signing, 524-535 [Zbl 0973.94540] \textit{Karhumäki, Juhani; Petre, Ion}, On the centralizer of a finite set, 536-546 [Zbl 0973.68115] \textit{Neven, Frank; Schwentick, Thomas}, On the power of tree-walking automata, 547-560 [Zbl 0973.68116] \textit{Béal, Marie-Pierre; Carton, Olivier}, Determinization of transducers over infinite words, 561-570 [Zbl 0973.68113] \textit{Mehlhorn, Kurt}, Constraint programming and graph algorithms, 571-575 [Zbl 0973.68252] \textit{Alon, Noga; Kaplan, Haim; Krivelevich, Michael; Malkhi, Dahlia; Stern, Julien}, Scalable secure storage when half the system is faulty, 576-587 [Zbl 0973.68610] \textit{Boros, Endre; Gurvich, Vladimir; Khachiyan, Leonid; Makino, Kazuhisa}, Generating partial and multiple transversals of a hypergraph, 588-599 [Zbl 0973.68182] \textit{Espírito Santo, José}, Revisiting the correspondence between cut elimination and normalisation, 600-611 [Zbl 0973.03073] \textit{Pichler, Reinhard}, Negation elimination from simple equational formulae, 612-623 [Zbl 0973.03014] \textit{Anil Kumar, V. S.; Arya, Sunil; Ramesh, H.}, Hardness of set cover with intersection 1, 624-635 [Zbl 0973.68080] \textit{Elkin, Michael; Peleg, David}, Strong inapproximability of the basic \(k\)-spanner problem. (Extended abstract), 636-647 [Zbl 0973.68525] \textit{Kuske, Dietrich}, Infinite series-parallel posets: Logic and languages, 648-662 [Zbl 0973.68164] \textit{Urbański, Tomasz Fryderyk}, On deciding if deterministic Rabin language is in Büchi class, 663-674 [Zbl 0973.03052] \textit{Henriksen, Jesper G.; Mukund, Madhavan; Kumar, K. Narayan; Thiagarajan, P. S.}, On message sequence graphs and finitely generated regular MSC languages, 675-686 [Zbl 0973.68042] \textit{Goldreich, Oded}, Pseudorandomness, 687-704 [Zbl 0973.68072] \textit{Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike}, A bound on the capacity of backoff and acknowledgement-based protocols, 705-716 [Zbl 0973.68011] \textit{Chlebus, Bogdan S.; Gąsieniec, Leszek; Östlin, Anna; Robson, John Michael}, Deterministic radio braodcasting, 717-728 [Zbl 0973.68501] \textit{Fokkink, W. J.; Luttik, S. P.}, An \(\omega\)-complete equational specification of interleaving. (Extended abstract), 729-743 [Zbl 0973.68533] \textit{Bravetti, Mario; Gorrieri, Roberto}, A complete axiomatziation for observational congruence of prioritized finite-state behaviors, 744-755 [Zbl 0973.68168] \textit{Adler, Micah; Fich, Faith; Goldberg, Leslie Ann; Paterson, Mike}, Tight size bounds for packet headers in narrow meshes, 756-767 [Zbl 0973.68502] \textit{Margara, Luciano; Simon, Janos}, Wavelength assignment problem on all-optical networks with \(k\) fibres per link, 768-779 [Zbl 0973.90502] \textit{Baier, Christel; Haverkort, Boudewijn; Hermanns, Holger; Katoen, Joost-Pieter}, On the logical characterisation of performability properties, 780-792 [Zbl 0973.68014] \textit{Bournez, Olivier; Maler, Oded}, On the representation of timed polyhedra, 793-807 [Zbl 0973.68143] \textit{Bender, Michael A.; Ron, Dana}, Testing acyclicity of directed graphs in sublinear time, 809-820 [Zbl 0973.05072] \textit{Djidjev, Hristo N.}, Computing the girth of a planar graph, 821-831 [Zbl 0973.05071] \textit{Fournier, Hervé; Koiran, Pascal}, Lower bounds are not easier over the reals: Inside PH, 832-843 [Zbl 0973.68081] \textit{Baliga, Ganesh; Case, John; Merkle, Wolfgang; Stephan, Frank}, Unlearning helps, 844-855 [Zbl 0973.68089] \textit{Czumaj, Artur; Lingas, Andrzej}, Fast approximation schemes for Euclidean multi-connectivity problems. (Extended abstract), 856-868 [Zbl 0973.90528] \textit{Grigni, Michelangelo}, Approximate TSP in graphs with forbidden minors, 869-877 [Zbl 0973.68263] \textit{Jansen, Klaus; Porkolab, Lorant}, Polynomial time approximation schemes for general multiprocessor job shop scheduling, 878-889 [Zbl 0973.68015] \textit{McKenzie, Pierre; Schwentick, Thomas; Thérien, Denis; Vollmer, Heribert}, The many faces of a translation, 890-901 [Zbl 0973.68155] \textit{Lutz, Jack H.}, Gales and the constructive dimension of individual sequences, 902-913 [Zbl 0973.68087] \textit{Merkle, Wolfgang}, The global power of additional queries to p-random oracles, 914-925 [Zbl 0973.03058] \textit{Buresh-Oppenheim, Josh; Pitassi, Toniann; Clegg, Matt; Impagliazzo, Russell}, Homogenization and the polynomial calculus, 926-937 [Zbl 0973.03013]