{"entities":{"Q1572745":{"pageid":1583485,"ns":120,"title":"Item:Q1572745","lastrevid":71327040,"modified":"2026-04-13T21:28:59Z","type":"item","id":"Q1572745","labels":{"en":{"language":"en","value":"Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9--15, 2000. Proceedings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1481745"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1572745$3C1226B1-DFF6-473D-9843-39A2A6B9F017","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c24bb04f436a848c7deb68f88def0a74be5c54b9","datavalue":{"value":{"text":"Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9--15, 2000. Proceedings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1572745$B9C16850-9540-47CC-BB9C-62E6B1F8A5F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"92303cbeca3f8d0dd8f197ad0a3a1bb9105fbb4e","datavalue":{"value":"0941.00034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1572745$C542412C-11C2-40E7-A8A5-8F895359F842","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bee6e450daaab34ac9322b600ecc454f9b4af050","datavalue":{"value":"10.1007/3-540-45022-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1572745$39013346-4C12-447F-8BDD-65D8BE1D6072","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1572745$D4A541CA-A161-4C59-A4C3-F45D013854CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0f0b15b8a0904033f22f1a331255b6cd52c7483","datavalue":{"value":{"time":"+2000-07-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1572745$3B28C94D-5F6E-41B6-B4F3-4627BB7414DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3760e464891cc63fe8182682d615a565957faf6d","datavalue":{"value":"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\u00e0, Ricard}, Monotone proofs of the pigeon hole principle, 151-162 [Zbl 0973.03074]  \\textit{L\u00fcttgen, 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\u010d, Juray; Karhum\u00e4ki, 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\u00f6ning, Uwe}, Deterministic algorithms for \\(k\\)-SAT based on covering codes and local search, 236-247 [Zbl 0973.68253]  \\textit{Bl\u00f6mer, 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\u00e1nos; Woeginger, Gerhard J.}, Resource augmentation for online bounded space bin packing. (Extended abstract), 296-304 [Zbl 0973.68529]  \\textit{Amb\u00fchl, Christoph; G\u00e4rtner, Bernd; von Stengel, Bernhard}, Optimal projective algorithms for the list update problem, 305-316 [Zbl 0973.68514]  \\textit{Ku\u010dera, Anton\u00edn}, 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\u00e9e, Brigitte}, Average bit-complexity of Euclidean algorithms, 373-387 [Zbl 0973.11102]  \\textit{Banderier, Cyril; Flajolet, Philippe; Schaeffer, Gilles; Soria, Mich\u00e8le}, Planar maps and Airy phenomena, 388-402 [Zbl 0973.05067]  \\textit{K\u00f6nig, 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\u00fcller, 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\u00e4ki, 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\u00e9al, 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\u00edrito Santo, Jos\u00e9}, 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\u0144ski, Tomasz Fryderyk}, On deciding if deterministic Rabin language is in B\u00fcchi 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\u0105sieniec, Leszek; \u00d6stlin, 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\u00e9; 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\u00e9rien, 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]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$76870B14-FEEA-4CA8-BCF5-631BE55F2AD2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f2c17db95e93f9a5a19ff6c68b3a1df8b0c021e","datavalue":{"value":"00B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1572745$5516984D-AB08-4887-BC22-ED759621B581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1572745$6DCF9E83-3AA7-45E6-A438-4FAA888AEE73","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"651131b79d1c5d4f2e5f93c4e03df783ec1a7a17","datavalue":{"value":"1481745","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1572745$4BEF0830-6261-4AE3-BED2-EB9A499BD236","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cf1ed8598d9d743d67a42b29ff4181d5264a34d","datavalue":{"value":"Geneva (Switzerland)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$91F6F9FC-F1AC-42AB-BD41-F595A92B0C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c4c4bb5a86a0fdf66f908b603f2f6975f5ef6fc","datavalue":{"value":"Proceedings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$FC4AF3C4-C79B-4560-A57B-AE3497ACDA95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85413872e180f82c5b8a578e96e74f0315026938","datavalue":{"value":"Colloquium","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$B88400C2-95E1-4307-83A1-12F01C943FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a97109b0450b9d75dc4782454065152e3832f948","datavalue":{"value":"ICALP 2000","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$F379FF2A-94F9-4FF4-906D-5C830594FF5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fff7125545fcdacaefe3808a1a5f0e0a281b403","datavalue":{"value":"Automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$08C72D84-9D20-4105-A1F3-D78999C38C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ec8e8b0049b2993c302f718ff35544cfb0150a0","datavalue":{"value":"Languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$2BBA6773-2D85-4788-A959-D54A2DD1FD01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c11b645d72aab44f88706dc65aaed7361e2cc1","datavalue":{"value":"Programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1572745$2C19B120-BDA9-4FD7-AC4B-E19F2E309394","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1572745$FAC735AB-3E54-4D5F-9B0D-B3AB63BB1E06","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9--15, 2000. Proceedings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Automata,_languages_and_programming._27th_international_colloquium,_ICALP_2000,_Geneva,_Switzerland,_July_9--15,_2000._Proceedings"}}}}}