×

zbMATH — the first resource for mathematics

Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. (English) Zbl 1029.00041
Lecture Notes in Computer Science. 2719. Berlin: Springer. xviii, 1199 p. EUR 95.00/net; $ 124.00; £73.00; sFr 158.00 (2003).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding colloquiuum has been reviewed (see Zbl 0993.00041).
Indexed articles:
Bergstra, Jan A.; Bethke, Inge, Polarized process algebra and program equivalence, 1-21 [Zbl 1039.68040]
Condon, Anne, Problems on RNA secondary structure prediction and design, 22-32 [Zbl 1060.68634]
Fiat, Amos, Some issues regarding search, censorship, and anonymity in peer to peer networks, 33 [Zbl 1039.68512]
Mutzel, Petra, The SPQR-tree data structure in graph drawing, 34-46 [Zbl 1039.68547]
Peled, Doron, Model checking and testing combined, 47-63 [Zbl 1039.68075]
Vardi, Moshe Y., Logic and automata: A match made in heaven, 64-65 [Zbl 1039.03508]
Hromkovič, Juraj; Schnitger, Georg, Pushdown automata and multicounter machines, a comparison of computation modes, 66-80 [Zbl 1039.68554]
De Bonis, Annalisa; Gasieniec, Leszek; Vaccaro, Ugo, Generalized framework for selectors with applications in optimal group testing, 81-96 [Zbl 1039.68116]
Bleichenbacher, Daniel; Kiayias, Aggelos; Yung, Moti, Decoding of interleaved Reed Solomon codes over noisy data, 97-108 [Zbl 1042.94529]
Blom, Stefan; Fokkink, Wan; Nain, Sumit, On the axiomatizability of ready traces, ready simulation, and failure traces, 109-118 [Zbl 1039.68081]
Gorla, Daniele; Pugliese, Rosario, Resource access and mobility control with dynamic privileges acquisition, 119-132 [Zbl 1039.68542]
Busi, Nadia; Gabbrielli, Maurizio; Zavattaro, Gianluigi, Replication vs. recursive definitions in channel based calculi, 133-144 [Zbl 1039.68082]
Ageev, Alexander; Ye, Yinyu; Zhang, Jiawei, Improved combinatorial approximation algorithms for the \(k\)-level facility location problem, 145-156 [Zbl 1060.90677]
Bläser, Markus, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, 157-163 [Zbl 1060.90694]
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]
Arora, Sanjeev; Chang, Kevin L., Approximation schemes for degree-restricted MST and red-blue separation problem, 176-188 [Zbl 1039.68165]
Chekuri, Chandra; Guha, Sudipto; Naor, Joseph, Approximating Steiner \(k\)-cuts, 189-199 [Zbl 1039.68166]
Coja-Oghlan, Amin; Moore, Cristopher; Sanwalani, Vishal, MAX \(k\)-CUT and approximating the chromatic number of random graphs, 200-211 [Zbl 1039.68167]
Elkin, Michael; Kortsarz, Guy, Approximation algorithm for directed telephone multicast problem, 212-223 [Zbl 1039.68511]
Ancona, Davide; Fagorzi, Sonia; Moggi, Eugenio; Zucca, Elena, Mixin modules and computational effects, 224-238 [Zbl 1039.68541]
Okhotin, Alexander, Decision problems for language equations with Boolean operations, 239-251 [Zbl 1039.68069]
Bruni, Roberto; Meseguer, José, Generalized rewrite theories, 252-266 [Zbl 1039.03020]
Antunes, Luís; Fortnow, Lance, Sophistication revisited, 267-277 [Zbl 1039.68058]
Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira, Scaled dimension and nonuniform complexity, 278-290 [Zbl 1039.68052]
Høyer, Peter; Mosca, Michele; de Wolf, Ronald, Quantum search on bounded-error inputs, 291-299 [Zbl 1039.68056]
Jain, Rahul; Radhakrishnan, Jaikumar; Sen, Pranab, A direct sum theorem in communication complexity via message compression, 300-315 [Zbl 1039.68048]
Franceschini, Gianni; Grossi, Roberto, Optimal cache-oblivious implicit dictionaries, 316-331 [Zbl 1039.68041]
Gál, Anna; Miltersen, Peter Bro, The cell probe complexity of succinct data structures, 332-344 [Zbl 1039.68544]
Munro, J. Ian; Raman, Rajeev; Raman, Venkatesh; Rao, Satti Srinivasa, Succinct representations of permutations, 345-356 [Zbl 1039.68546]
Raman, Rajeev; Rao, Satti Srinivasa, Succinct dynamic dictionaries and trees, 357-368 [Zbl 1039.68043]
Korman, Amos; Peleg, David, Labeling schemes for weighted dynamic trees, 369-383 [Zbl 1039.68513]
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]
Hall, Alex; Hippler, Steffen; Skutella, Martin, Multicommodity flows over time: Efficient algorithms and complexity, 397-409 [Zbl 1060.90512]
Chekuri, Chandra; Mydlarz, Marcelo; Shepherd, F. Bruce, Multicommodity demand flow in a tree, 410-425 [Zbl 1060.90511]
Droste, Manfred; Kuske, Dietrich, Skew and infinitary formal power series, 426-438 [Zbl 1039.68065]
Hromkovič, Juraj; Schnitger, Georg, Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation, 439-451 [Zbl 1039.68068]
Denis, François; Esposito, Yann, Residual languages and probabilistic automata, 452-463 [Zbl 1039.68064]
Stoelinga, Mariëlle; Vaandrager, Frits, A testing scenario for probabilistic automata, 464-477 [Zbl 1039.68071]
Sénizergues, Géraud, The equivalence problem for \(t\)-turn DPDA is co-NP, 478-489 [Zbl 1039.68070]
Holzer, Markus; Kutrib, Martin, Flip-pushdown automata: \(k+1\) pushdown reversals are better than \(k\), 490-501 [Zbl 1039.68066]
Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay, Convergence time to Nash equilibria, 502-513 [Zbl 1039.68017]
Feldmann, Rainer; Gairing, Martin; Lücking, Thomas; Monien, Burkhard; Rode, Manuel, Nashification and the coordination ratio for a selfish routing game, 514-526 [Zbl 1060.68531]
Bansal, Vipul; Agrawal, Aseem; Malhotra, Varun S., Stable marriages with multiple partners: Efficient search for an optimal solution, 527-542 [Zbl 1060.91514]
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]
Cachat, Thierry, Higher order pushdown automata, the Caucal hierarchy of graphs and parity games, 556-569 [Zbl 1039.68063]
Mayr, Richard, Undecidability of weak bisimulation equivalence for 1-counter processes, 570-583 [Zbl 1039.68084]
Merro, Massimo; Nardelli, Francesco Zappa, Bisimulation proof methods for mobile ambients, 584-598 [Zbl 1039.68085]
Carayol, Arnaud; Colcombet, Thomas, On equivalent representations of infinite structures, 599-610 [Zbl 1039.03021]
Schönhage, Arnold, Adaptive raising strategies optimizing relative efficiency, 611-623 [Zbl 1039.68123]
Sitters, René A.; Stougie, Leen; de Paepe, Willem E., A competitive algorithm for the general 2-server problem, 624-636 [Zbl 1039.68124]
Fotakis, Dimitris, On the competitive ratio for online facility location, 637-652 [Zbl 1039.68117]
Albers, Susanne; van Stee, Rob, A study of integrated document and connection caching, 653-667 [Zbl 1039.68509]
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]
Klaedtke, Felix; Rueß, Harald, Monadic second-order logics with cardinalities, 681-696 [Zbl 1039.03004]
Kupferman, Orna; Vardi, Moshe Y., \(\Pi_2 \cap \Sigma_2 \equiv \text{AFMC}\), 697-713 [Zbl 1039.03023]
Rybina, Tatiana; Voronkov, Andrei, Upper bounds for a theory of queues, 714-724 [Zbl 1039.03005]
Berger, Noam; Bollobás, Béla; Borgs, Christian; Chayes, Jennifer; Riordan, Oliver, Degree distribution of the FKP network model, 725-738 [Zbl 1039.68510]
Blondel, Vincent D.; Van Dooren, Paul, Similarity matrices for pairs of graphs, 739-750 [Zbl 1039.68089]
Bhatia, Randeep; Chuzhoy, Julia; Freund, Ari; Naor, Joseph, Algorithmic aspects of bandwidth trading, 751-766 [Zbl 1039.68535]
Johannsen, Jan; Lange, Martin, CTL\(^{+}\) is complete for double exponential time, 767-775 [Zbl 1039.68073]
La Torre, Salvatore; Napoli, Margherita; Parente, Mimmo; Parlato, Gennaro, Hierarchical and recursive state machines with context-dependent properties, 776-789 [Zbl 1039.68074]
Schnoebelen, Philippe, Oracle circuits for branching-time model checking, 790-801 [Zbl 1039.68076]
Gargano, Luisa; Hammar, Mikael, There are spanning spiders in dense graphs (and we know how to find them), 802-816 [Zbl 1039.68095]
Fiala, Jiří; Paulusma, Daniël, The computational complexity of the role assignment problem, 817-828 [Zbl 1039.68094]
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]
Chen, Jianer; Kanj, Iyad A.; Perković, Ljubomir; Sedgwick, Eric; Xia, Ge, Genus characterizes the complexity of graph problems: Some tight results, 845-856 [Zbl 1039.68092]
Eisner, Cindy; Fisman, Dana; Havlicek, John; McIsaac, Anthony; Van Campenhout, David, The definition of a temporal clock operator, 857-870 [Zbl 1039.03505]
Ariola, Zena M.; Herbelin, Hugo, Minimal classical logic and control operators, 871-885 [Zbl 1039.03019]
Henzinger, Thomas A.; Jhala, Ranjit; Majumdar, Rupak, Counterexample-guided control, 886-902 [Zbl 1039.68555]
Hannay, Jo, Axiomatic criteria for quotients and subobjects for higher-order data types, 903-917 [Zbl 1039.68079]
Matias, Yossi; Porat, Ely, Efficient pebbling for list traversal synopses, 918-928 [Zbl 1039.68545]
Amir, Amihood; Aumann, Yonatan; Cole, Richard; Lewenstein, Moshe; Porat, Ely, Function matching: Algorithms, applications, and a lower bound, 929-942 [Zbl 1039.68933]
Kärkkäinen, Juha; Sanders, Peter, Simple linear work suffix array construction, 943-955 [Zbl 1039.68042]
Gutiérrez, Francisco; Ruiz, Blas, Expansion postponement via cut elimination in sequent calculi for pure type systems, 956-968 [Zbl 1039.03045]
Bugliesi, Michele; Crafa, Silvia; Prelic, Amela; Sassone, Vladimiro, Secrecy in untrusted networks, 969-983 [Zbl 1039.68516]
Chattopadhyay, Arkadev; Thérien, Denis, Locally commutative categories, 984-995 [Zbl 1041.18005]
Doberkat, Ernst-Erich, Semi-pullbacks and bisimulations in categories of stochastic relations, 996-1007 [Zbl 1041.18006]
Rabinovich, Alexander, Quantitative analysis of probabilistic lossy channel systems, 1008-1021 [Zbl 1039.68557]
de Alfaro, Luca; Henzinger, Thomas A.; Majumdar, Rupak, Discounting the future in systems theory, 1022-1037 [Zbl 1039.68087]
de Alfaro, Luca; Faella, Marco, Information flow in concurrent games, 1038-1053 [Zbl 1039.68086]
Ikeda, Satoshi; Kubo, Izumi; Okumoto, Norihiro; Yamashita, Masafumi, Impact of local topological information on random walks on finite graphs, 1054-1067 [Zbl 1040.60037]
Jägersküpper, Jens, Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces, 1068-1079 [Zbl 1039.68586]
Poulalhon, Dominique; Schaeffer, Gilles, Optimal coding and sampling of triangulations, 1080-1094 [Zbl 1039.05028]
Bodirsky, Manuel; Gröpl, Clemens; Kang, Mihyun, Generating labeled planar graphs uniformly at random, 1095-1107 [Zbl 1039.05057]
Crescenzi, Pilu; Gambosi, Giorgio; Nicosia, Gaia; Penna, Paolo; Unger, Walter, Online load balancing made simple: Greedy strikes back, 1108-1122 [Zbl 1039.68536]
Naor, Joseph; Shachnai, Hadas; Tamir, Tami, Real-time scheduling with a budget, 1123-1137 [Zbl 1039.68018]
Dean, Brian C.; Goemans, Michel X., Improved approximation algorithms for minimum-space advertisement scheduling, 1138-1152 [Zbl 1039.68537]
Awerbuch, Baruch; Brinkmann, André; Scheideler, Christian, Anycasting in adversarial systems: Routing and admission control, 1153-1168 [Zbl 1039.68534]
Bespamyatnikh, Sergei; Segal, Michael, Dynamic algorithms for approximating interdistances, 1169-1180 [Zbl 1039.68768]
Cieliebak, Mark; Flocchini, Paola; Prencipe, Giuseppe; Santoro, Nicola, Solving the robots gathering problem, 1181-1196 [Zbl 1039.68129]

MSC:
00B25 Proceedings of conferences of miscellaneous specific interest
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Nxx Theory of software
68Qxx Theory of computing
PDF BibTeX XML Cite
Full Text: Link