Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9–15, 2000. Proceedings. (English) Zbl 0941.00034

Lecture Notes in Computer Science. 1853. Berlin: Springer. xvi, 941 p. (2000).

Show indexed articles as search result.

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


00B25 Proceedings of conferences of miscellaneous specific interest
68-06 Proceedings, conferences, collections, etc. pertaining to computer science


Zbl 0917.00014
Full Text: DOI