{"entities":{"Q5941726":{"pageid":8118528,"ns":120,"title":"Item:Q5941726","lastrevid":32842802,"modified":"2024-03-20T00:42:46Z","type":"item","id":"Q5941726","labels":{"en":{"language":"en","value":"Automata, languages and programming. 28th international colloquium, ICALP 2001, Crete, Greece, July 8--12, 2001. Proceedings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1636389"}},"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":"Q5941726$30EDA836-9B2B-4DA5-B291-2A4827B2A4F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9edca59214c165bced31f6d4606cb1a1a4413f7","datavalue":{"value":{"text":"Automata, languages and programming. 28th international colloquium, ICALP 2001, Crete, Greece, July 8--12, 2001. Proceedings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941726$49D18102-53B9-4687-A1D6-CFE33A65C959","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5350a9d3973a88f2a8d071a22e311c8a6771518","datavalue":{"value":"0967.00069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$252867C5-1968-4E34-9559-2BD6D56A8936","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b402cdcf1e7801ae669629cc44a31b5227186d19","datavalue":{"value":"10.1007/3-540-48224-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$00B59D10-1149-46EF-885F-A41DA1906975","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":"Q5941726$5BE5BEFB-E428-45CB-9042-1C64995D8C9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c3190f357053ae1b7a6692b25e4aa81e02b63efa","datavalue":{"value":{"time":"+2001-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941726$FBF2EF71-EAFB-4EB4-AC0A-DC22A5D155B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"904fd81764d81d0d495c6cec2d6ce7d5d1e391fa","datavalue":{"value":"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\u00dfe-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\u00e4ser, 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\u00f8lting; Fagerberg, Rolf; Pedersen, Christian N. S.; \u00d6stlin, Anna}, The complexity of constructing evolutionary trees using experiments, 140-151 [Zbl 0986.68100]  \\textit{Flajolet, Philippe; Guivarc'h, Yves; Szpankowski, Wojciech; Vall\u00e9e, 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\u00fcrer, 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\u00f8yer, 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\u00e9rard; 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.; \u1e62ahinalp, S\u00fcleyman 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\u010d, 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\u00e9bastien; Holton, Charles; Zamboni, Luca Q.}, Combinatorics of three-interval exchanges, 567-578 [Zbl 0986.68102]  \\textit{Harju, Tero; Ibarra, Oscar; Karhum\u00e4ki, 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\u00e9ronique; 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\u00fcchi 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\u00e9rennes, St\u00e9phane; Rivano, Herv\u00e9}, 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\u00e1nos; Imreh, Csan\u00e1d; Noga, John; Sgall, Ji\u0159\u00ed}, 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\u00f6der, Lutz; Mossakowski, Till; Tarlecki, Andrzej}, Amalgamation in CASL via enriched signatures, 993-1004 [Zbl 0986.68015]  \\textit{Atserias, Albert; Bonet, Mar\u00eda Luisa; Esteban, Juan Luis}, Lower bounds for the weak pigeonhole principle beyond resolution, 1005-1016 [Zbl 0986.03046]  \\textit{Buhrman, Harry; Tromp, John; Vit\u00e1nyi, 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\u0144ski, Tomasz; Kuty\u0142owski, Miros\u0142aw}, 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]","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$5AC2E4C8-1266-4C3C-ADF9-4972ACEBC35B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f2c17db95e93f9a5a19ff6c68b3a1df8b0c021e","datavalue":{"value":"00B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$7780304D-9EA0-449B-9C44-15E6722530A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$D2948032-298D-4E9D-8428-4F158CD623CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d59aa4d003df9e50545d4e5097ff99b8f5e8633c","datavalue":{"value":"1636389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$48A5C02D-1C9E-4E03-AC48-B22919EED8F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d76ae8c8443baab8abd35456a3dfd4ab517e80c6","datavalue":{"value":"Crete (Greece)","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$2D5009F3-ED52-4E2A-9096-7053EBF0964B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85413872e180f82c5b8a578e96e74f0315026938","datavalue":{"value":"Colloquium","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$47751EFF-EEC5-436A-8FF5-CBE1334C789B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c4c4bb5a86a0fdf66f908b603f2f6975f5ef6fc","datavalue":{"value":"Proceedings","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$8AC2D1D1-E4CE-47BA-ADFC-6A9DFE80B913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60e41b0108317f8110920c9e7c951800c2a39a83","datavalue":{"value":"ICALP 2001","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$C9B27E02-EF87-4761-8F2E-AB4AF94F427C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fff7125545fcdacaefe3808a1a5f0e0a281b403","datavalue":{"value":"Automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$B857DB47-1FB1-4BA0-A127-6B7C01F133B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ec8e8b0049b2993c302f718ff35544cfb0150a0","datavalue":{"value":"Languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$86537096-3F9F-454C-B787-475C8B20E560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c11b645d72aab44f88706dc65aaed7361e2cc1","datavalue":{"value":"Programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941726$19AC6A5B-E9E8-46B9-860D-0AE578A69BAB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"93c0230c09d80ebaffe417c4930b3cf62c7a1ede","datavalue":{"value":"Q56282717","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$9F27679C-6BFC-41B3-BFB1-3F59DA82813D","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":"Q5941726$3F901EC2-24D4-41EA-AEE6-2734937BEFB7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"08f013481f30dc0a96f0b8fe2d1c2176aaf722ae","datavalue":{"value":"https://doi.org/10.1007/3-540-48224-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q5941726$02010258-BF8D-4755-8BD5-C56543CD0E49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6c39b2f129ba0995b92b182b9dad82f6c1b41bb3","datavalue":{"value":"W4383679771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941726$599D51F9-DEDB-40CE-B7B9-529B4D24204C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941726","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941726"}}}}}