{"entities":{"Q1419516":{"pageid":1430256,"ns":120,"title":"Item:Q1419516","lastrevid":68659749,"modified":"2026-04-13T01:15:07Z","type":"item","id":"Q1419516","labels":{"en":{"language":"en","value":"Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 -- July 4, 2003. Proceedings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2027294"}},"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":"Q1419516$956E546F-3DB2-4E40-999C-9A5DADD64727","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec7ecafc1ec8484dec78d8039013f85e85d207dc","datavalue":{"value":{"text":"Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 -- July 4, 2003. Proceedings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1419516$F8B2488D-854F-4722-85B0-1A5D92AEE455","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d3e003f46583c331f212abad2717af19afdb91c","datavalue":{"value":"1029.00041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$A5C9FC66-FE44-485F-A6E6-4DB9BA2C69C4","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":"Q1419516$708A7913-2CBB-4BB9-BCA9-F3341BE94839","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ad5e0ccb1f33d4e953d3cbe4e608e42b46cc271a","datavalue":{"value":{"time":"+2004-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1419516$BA61358A-73A2-443C-9DE3-DAA656FFF412","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0534fc270cba37dc0c3f42e94c6286f8ead8100f","datavalue":{"value":"http://link.springer.de/link/service/series/0558/tocs/t2719.htm","type":"string"},"datatype":"url"},"type":"statement","id":"Q1419516$9C53FBB3-68A4-44D1-BE96-46C4929197B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de7e6d6da97b493c1f2b2fba1e886ea6159fad64","datavalue":{"value":"The articles of this volume will be reviewed individually. The preceding colloquiuum has been reviewed (see Zbl 0993.00041).  Indexed articles:  \\textit{Bergstra, Jan A.; Bethke, Inge}, Polarized process algebra and program equivalence, 1-21 [Zbl 1039.68040]  \\textit{Condon, Anne}, Problems on RNA secondary structure prediction and design, 22-32 [Zbl 1060.68634]  \\textit{Fiat, Amos}, Some issues regarding search, censorship, and anonymity in peer to peer networks, 33 [Zbl 1039.68512]  \\textit{Mutzel, Petra}, The SPQR-tree data structure in graph drawing, 34-46 [Zbl 1039.68547]  \\textit{Peled, Doron}, Model checking and testing combined, 47-63 [Zbl 1039.68075]  \\textit{Vardi, Moshe Y.}, Logic and automata: A match made in heaven, 64-65 [Zbl 1039.03508]  \\textit{Hromkovi\u010d, Juraj; Schnitger, Georg}, Pushdown automata and multicounter machines, a comparison of computation modes, 66-80 [Zbl 1039.68554]  \\textit{De Bonis, Annalisa; Gasieniec, Leszek; Vaccaro, Ugo}, Generalized framework for selectors with applications in optimal group testing, 81-96 [Zbl 1039.68116]  \\textit{Bleichenbacher, Daniel; Kiayias, Aggelos; Yung, Moti}, Decoding of interleaved Reed Solomon codes over noisy data, 97-108 [Zbl 1042.94529]  \\textit{Blom, Stefan; Fokkink, Wan; Nain, Sumit}, On the axiomatizability of ready traces, ready simulation, and failure traces, 109-118 [Zbl 1039.68081]  \\textit{Gorla, Daniele; Pugliese, Rosario}, Resource access and mobility control with dynamic privileges acquisition, 119-132 [Zbl 1039.68542]  \\textit{Busi, Nadia; Gabbrielli, Maurizio; Zavattaro, Gianluigi}, Replication vs. recursive definitions in channel based calculi, 133-144 [Zbl 1039.68082]  \\textit{Ageev, Alexander; Ye, Yinyu; Zhang, Jiawei}, Improved combinatorial approximation algorithms for the \\(k\\)-level facility location problem, 145-156 [Zbl 1060.90677]  \\textit{Bl\u00e4ser, Markus}, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, 157-163 [Zbl 1060.90694]  \\textit{Gandhi, Rajiv; Halperin, Eran; Khuller, Samir; Kortsarz, Guy; Srinivasan, Aravind}, An improved approximation algorithm for vertex cover with hard capacities (extended abstract), 164-175 [Zbl 1060.68694]  \\textit{Arora, Sanjeev; Chang, Kevin L.}, Approximation schemes for degree-restricted MST and red-blue separation problem, 176-188 [Zbl 1039.68165]  \\textit{Chekuri, Chandra; Guha, Sudipto; Naor, Joseph}, Approximating Steiner \\(k\\)-cuts, 189-199 [Zbl 1039.68166]  \\textit{Coja-Oghlan, Amin; Moore, Cristopher; Sanwalani, Vishal}, MAX \\(k\\)-CUT and approximating the chromatic number of random graphs, 200-211 [Zbl 1039.68167]  \\textit{Elkin, Michael; Kortsarz, Guy}, Approximation algorithm for directed telephone multicast problem, 212-223 [Zbl 1039.68511]  \\textit{Ancona, Davide; Fagorzi, Sonia; Moggi, Eugenio; Zucca, Elena}, Mixin modules and computational effects, 224-238 [Zbl 1039.68541]  \\textit{Okhotin, Alexander}, Decision problems for language equations with Boolean operations, 239-251 [Zbl 1039.68069]  \\textit{Bruni, Roberto; Meseguer, Jos\u00e9}, Generalized rewrite theories, 252-266 [Zbl 1039.03020]  \\textit{Antunes, Lu\u00eds; Fortnow, Lance}, Sophistication revisited, 267-277 [Zbl 1039.68058]  \\textit{Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira}, Scaled dimension and nonuniform complexity, 278-290 [Zbl 1039.68052]  \\textit{H\u00f8yer, Peter; Mosca, Michele; de Wolf, Ronald}, Quantum search on bounded-error inputs, 291-299 [Zbl 1039.68056]  \\textit{Jain, Rahul; Radhakrishnan, Jaikumar; Sen, Pranab}, A direct sum theorem in communication complexity via message compression, 300-315 [Zbl 1039.68048]  \\textit{Franceschini, Gianni; Grossi, Roberto}, Optimal cache-oblivious implicit dictionaries, 316-331 [Zbl 1039.68041]  \\textit{G\u00e1l, Anna; Miltersen, Peter Bro}, The cell probe complexity of succinct data structures, 332-344 [Zbl 1039.68544]  \\textit{Munro, J. Ian; Raman, Rajeev; Raman, Venkatesh; Rao, Satti Srinivasa}, Succinct representations of permutations, 345-356 [Zbl 1039.68546]  \\textit{Raman, Rajeev; Rao, Satti Srinivasa}, Succinct dynamic dictionaries and trees, 357-368 [Zbl 1039.68043]  \\textit{Korman, Amos; Peleg, David}, Labeling schemes for weighted dynamic trees, 369-383 [Zbl 1039.68513]  \\textit{Baswana, Surender; Sen, Sandeep}, A simple linear time algorithm for computing a \\((2k-1)\\)-spanner of \\(O(n^{1+1/k})\\) size in weighted graphs, 384-396 [Zbl 1039.05056]  \\textit{Hall, Alex; Hippler, Steffen; Skutella, Martin}, Multicommodity flows over time: Efficient algorithms and complexity, 397-409 [Zbl 1060.90512]  \\textit{Chekuri, Chandra; Mydlarz, Marcelo; Shepherd, F. Bruce}, Multicommodity demand flow in a tree, 410-425 [Zbl 1060.90511]  \\textit{Droste, Manfred; Kuske, Dietrich}, Skew and infinitary formal power series, 426-438 [Zbl 1039.68065]  \\textit{Hromkovi\u010d, Juraj; Schnitger, Georg}, Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser's separation, 439-451 [Zbl 1039.68068]  \\textit{Denis, Fran\u00e7ois; Esposito, Yann}, Residual languages and probabilistic automata, 452-463 [Zbl 1039.68064]  \\textit{Stoelinga, Mari\u00eblle; Vaandrager, Frits}, A testing scenario for probabilistic automata, 464-477 [Zbl 1039.68071]  \\textit{S\u00e9nizergues, G\u00e9raud}, The equivalence problem for \\(t\\)-turn DPDA is co-NP, 478-489 [Zbl 1039.68070]  \\textit{Holzer, Markus; Kutrib, Martin}, Flip-pushdown automata: \\(k+1\\) pushdown reversals are better than \\(k\\), 490-501 [Zbl 1039.68066]  \\textit{Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay}, Convergence time to Nash equilibria, 502-513 [Zbl 1039.68017]  \\textit{Feldmann, Rainer; Gairing, Martin; L\u00fccking, Thomas; Monien, Burkhard; Rode, Manuel}, Nashification and the coordination ratio for a selfish routing game, 514-526 [Zbl 1060.68531]  \\textit{Bansal, Vipul; Agrawal, Aseem; Malhotra, Varun S.}, Stable marriages with multiple partners: Efficient search for an optimal solution, 527-542 [Zbl 1060.91514]  \\textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid; Makino, Kazuhisa}, An intersection inequality for discrete distributions and related generation problems, 543-555 [Zbl 1060.90691]  \\textit{Cachat, Thierry}, Higher order pushdown automata, the Caucal hierarchy of graphs and parity games, 556-569 [Zbl 1039.68063]  \\textit{Mayr, Richard}, Undecidability of weak bisimulation equivalence for 1-counter processes, 570-583 [Zbl 1039.68084]  \\textit{Merro, Massimo; Nardelli, Francesco Zappa}, Bisimulation proof methods for mobile ambients, 584-598 [Zbl 1039.68085]  \\textit{Carayol, Arnaud; Colcombet, Thomas}, On equivalent representations of infinite structures, 599-610 [Zbl 1039.03021]  \\textit{Sch\u00f6nhage, Arnold}, Adaptive raising strategies optimizing relative efficiency, 611-623 [Zbl 1039.68123]  \\textit{Sitters, Ren\u00e9 A.; Stougie, Leen; de Paepe, Willem E.}, A competitive algorithm for the general 2-server problem, 624-636 [Zbl 1039.68124]  \\textit{Fotakis, Dimitris}, On the competitive ratio for online facility location, 637-652 [Zbl 1039.68117]  \\textit{Albers, Susanne; van Stee, Rob}, A study of integrated document and connection caching, 653-667 [Zbl 1039.68509]  \\textit{Xie, Gaoyan; Dang, Zhe; Ibarra, Oscar H.}, A solvable class of quadratic Diophantine equations with applications to verification of infinite-state systems, 668-680 [Zbl 1039.68077]  \\textit{Klaedtke, Felix; Rue\u00df, Harald}, Monadic second-order logics with cardinalities, 681-696 [Zbl 1039.03004]  \\textit{Kupferman, Orna; Vardi, Moshe Y.}, \\(\\Pi_2 \\cap \\Sigma_2 \\equiv \\text{AFMC}\\), 697-713 [Zbl 1039.03023]  \\textit{Rybina, Tatiana; Voronkov, Andrei}, Upper bounds for a theory of queues, 714-724 [Zbl 1039.03005]  \\textit{Berger, Noam; Bollob\u00e1s, B\u00e9la; Borgs, Christian; Chayes, Jennifer; Riordan, Oliver}, Degree distribution of the FKP network model, 725-738 [Zbl 1039.68510]  \\textit{Blondel, Vincent D.; Van Dooren, Paul}, Similarity matrices for pairs of graphs, 739-750 [Zbl 1039.68089]  \\textit{Bhatia, Randeep; Chuzhoy, Julia; Freund, Ari; Naor, Joseph}, Algorithmic aspects of bandwidth trading, 751-766 [Zbl 1039.68535]  \\textit{Johannsen, Jan; Lange, Martin}, CTL\\(^{+}\\) is complete for double exponential time, 767-775 [Zbl 1039.68073]  \\textit{La Torre, Salvatore; Napoli, Margherita; Parente, Mimmo; Parlato, Gennaro}, Hierarchical and recursive state machines with context-dependent properties, 776-789 [Zbl 1039.68074]  \\textit{Schnoebelen, Philippe}, Oracle circuits for branching-time model checking, 790-801 [Zbl 1039.68076]  \\textit{Gargano, Luisa; Hammar, Mikael}, There are spanning spiders in dense graphs (and we know how to find them), 802-816 [Zbl 1039.68095]  \\textit{Fiala, Ji\u0159\u00ed; Paulusma, Dani\u00ebl}, The computational complexity of the role assignment problem, 817-828 [Zbl 1039.68094]  \\textit{Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.}, Fixed-parameter algorithms for the \\((k,r)\\)-center in planar graphs and map graphs, 829-844 [Zbl 1039.68093]  \\textit{Chen, Jianer; Kanj, Iyad A.; Perkovi\u0107, Ljubomir; Sedgwick, Eric; Xia, Ge}, Genus characterizes the complexity of graph problems: Some tight results, 845-856 [Zbl 1039.68092]  \\textit{Eisner, Cindy; Fisman, Dana; Havlicek, John; McIsaac, Anthony; Van Campenhout, David}, The definition of a temporal clock operator, 857-870 [Zbl 1039.03505]  \\textit{Ariola, Zena M.; Herbelin, Hugo}, Minimal classical logic and control operators, 871-885 [Zbl 1039.03019]  \\textit{Henzinger, Thomas A.; Jhala, Ranjit; Majumdar, Rupak}, Counterexample-guided control, 886-902 [Zbl 1039.68555]  \\textit{Hannay, Jo}, Axiomatic criteria for quotients and subobjects for higher-order data types, 903-917 [Zbl 1039.68079]  \\textit{Matias, Yossi; Porat, Ely}, Efficient pebbling for list traversal synopses, 918-928 [Zbl 1039.68545]  \\textit{Amir, Amihood; Aumann, Yonatan; Cole, Richard; Lewenstein, Moshe; Porat, Ely}, Function matching: Algorithms, applications, and a lower bound, 929-942 [Zbl 1039.68933]  \\textit{K\u00e4rkk\u00e4inen, Juha; Sanders, Peter}, Simple linear work suffix array construction, 943-955 [Zbl 1039.68042]  \\textit{Guti\u00e9rrez, Francisco; Ruiz, Blas}, Expansion postponement via cut elimination in sequent calculi for pure type systems, 956-968 [Zbl 1039.03045]  \\textit{Bugliesi, Michele; Crafa, Silvia; Prelic, Amela; Sassone, Vladimiro}, Secrecy in untrusted networks, 969-983 [Zbl 1039.68516]  \\textit{Chattopadhyay, Arkadev; Th\u00e9rien, Denis}, Locally commutative categories, 984-995 [Zbl 1041.18005]  \\textit{Doberkat, Ernst-Erich}, Semi-pullbacks and bisimulations in categories of stochastic relations, 996-1007 [Zbl 1041.18006]  \\textit{Rabinovich, Alexander}, Quantitative analysis of probabilistic lossy channel systems, 1008-1021 [Zbl 1039.68557]  \\textit{de Alfaro, Luca; Henzinger, Thomas A.; Majumdar, Rupak}, Discounting the future in systems theory, 1022-1037 [Zbl 1039.68087]  \\textit{de Alfaro, Luca; Faella, Marco}, Information flow in concurrent games, 1038-1053 [Zbl 1039.68086]  \\textit{Ikeda, Satoshi; Kubo, Izumi; Okumoto, Norihiro; Yamashita, Masafumi}, Impact of local topological information on random walks on finite graphs, 1054-1067 [Zbl 1040.60037]  \\textit{J\u00e4gersk\u00fcpper, Jens}, Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces, 1068-1079 [Zbl 1039.68586]  \\textit{Poulalhon, Dominique; Schaeffer, Gilles}, Optimal coding and sampling of triangulations, 1080-1094 [Zbl 1039.05028]  \\textit{Bodirsky, Manuel; Gr\u00f6pl, Clemens; Kang, Mihyun}, Generating labeled planar graphs uniformly at random, 1095-1107 [Zbl 1039.05057]  \\textit{Crescenzi, Pilu; Gambosi, Giorgio; Nicosia, Gaia; Penna, Paolo; Unger, Walter}, Online load balancing made simple: Greedy strikes back, 1108-1122 [Zbl 1039.68536]  \\textit{Naor, Joseph; Shachnai, Hadas; Tamir, Tami}, Real-time scheduling with a budget, 1123-1137 [Zbl 1039.68018]  \\textit{Dean, Brian C.; Goemans, Michel X.}, Improved approximation algorithms for minimum-space advertisement scheduling, 1138-1152 [Zbl 1039.68537]  \\textit{Awerbuch, Baruch; Brinkmann, Andr\u00e9; Scheideler, Christian}, Anycasting in adversarial systems: Routing and admission control, 1153-1168 [Zbl 1039.68534]  \\textit{Bespamyatnikh, Sergei; Segal, Michael}, Dynamic algorithms for approximating interdistances, 1169-1180 [Zbl 1039.68768]  \\textit{Cieliebak, Mark; Flocchini, Paola; Prencipe, Giuseppe; Santoro, Nicola}, Solving the robots gathering problem, 1181-1196 [Zbl 1039.68129]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$0483A1C1-CDB4-4604-90E5-6790509C6CD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f2c17db95e93f9a5a19ff6c68b3a1df8b0c021e","datavalue":{"value":"00B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$47814C55-A785-4DCC-A8AD-F4BB7C24DD65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$A4DF7C39-2AD3-4C0F-87CD-4A28CBFAB513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1a86519cb3571ebce07f2774b2a00a0f17e12c3e","datavalue":{"value":"68Nxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$A326E915-DEFC-4357-88FE-674EB94056BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$393DCF15-0D0D-41D6-BE61-40CE467F18B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b43ab3b4857e6152ea59d19097bffc9a8703ccc8","datavalue":{"value":"2027294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$E604953E-AB37-4410-A8EF-957C633EB734","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fff7125545fcdacaefe3808a1a5f0e0a281b403","datavalue":{"value":"Automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$7F3D23F6-D360-454D-9A86-B6A56AC74192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ec8e8b0049b2993c302f718ff35544cfb0150a0","datavalue":{"value":"Languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$16220685-6F94-4600-BECC-1A91E0B69AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c11b645d72aab44f88706dc65aaed7361e2cc1","datavalue":{"value":"Programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$C1BDD417-37FB-4583-B5D1-D77399226843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7008ea9afa96de71c4ba6e2db17aad94f368ff19","datavalue":{"value":"ICALP 2003","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$578F8358-F62D-487C-87F6-6AACFEBB2ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8da3b4f25b771fb37e06da330f0494696eadee19","datavalue":{"value":"Eindhoven (The Netherlands)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1419516$74FC3A6B-8CAC-4399-BE62-2B3D47AF6560","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":"Q1419516$F69D0E1F-A0E1-4369-A93A-F7CE8FFB2006","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f6b93abed6a26c5234d563a4994d90ce76724144","datavalue":{"value":"10.1007/3-540-45061-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$C609ACF6-986C-4115-A2C0-E80CA38C773B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d59105250ecfbb8f4731ca2a9f0a43314fa55abe","datavalue":{"value":"W2102369166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1419516$D03D7969-1D31-4E71-8B25-078FCC847C9A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 -- July 4, 2003. Proceedings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Automata,_languages_and_programming._30th_international_colloquium,_ICALP_2003,_Eindhoven,_The_Netherland,_June_30_--_July_4,_2003._Proceedings"}}}}}