×

zbMATH — the first resource for mathematics

Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. (English) Zbl 0993.00041
Lecture Notes in Computer Science. 2380. Berlin: Springer. xxi, 1069 p. (2002).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding colloquium (28th, 2001) has been reviewed (see Zbl 0967.00069).
Indexed articles:
Reif, John H., Molecular assembly and computation: From theory to experimental demonstrations, 1-21 [Zbl 1056.68544]
Marathe, Madhav V., Towards a predictive computational complexity theory, 22-31 [Zbl 1056.68546]
Pitts, Andrew M., Equivariant syntax and semantics, 32-36 [Zbl 1056.68508]
Sénizergues, Géraud, \(L(A) \)=\( L(B)\)? decidability results from complete formal systems, 37 [Zbl 1056.68548]
Del Lungo, Alberto; Frosini, Andrea; Nivat, Maurice; Vuillon, Laurent, Discrete tomography: Reconstruction under periodicity constraints, 38-56 [Zbl 1056.68592]
Mannila, Heikki, Local and global methods in data mining: Basic techniques and open problems, 57-68 [Zbl 1056.68516]
Hermenegildo, M.; Puebla, G.; Bueno, F.; López-García, P., Program debugging and validation using semantic approximations and partial specifications, 69-72 [Zbl 1056.68509]
Engebretsen, Lars; Holmerin, Jonas; Russell, Alexander, Inapproximability results for equations over finite groups, 73-84 [Zbl 1056.68545]
Pettie, Seth, A faster all-pairs shortest path algorithm for real-weighted sparse graphs, 85-97 [Zbl 1056.68111]
Colcombet, Thomas, On families of graphs having a decidable first order theory with reachability, 98-109 [Zbl 1056.68107]
Fabrikant, Alex; Koutsoupias, Elias; Papadimitriou, Christos H., Heuristically optimized trade-offs: A new paradigm for power laws in the internet, 110-122 [Zbl 1056.68503]
Fotakis, Dimitris; Kontogiannis, Spyros; Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul, The structure and complexity of Nash equilibria for a selfish routing game, 123-134 [Zbl 1056.68028]
Khanna, Sanjeev; Naor, Joseph (Seffi); Raz, Dan, Control message aggregation in group communication protocols, 135-146 [Zbl 1056.68506]
Jurdziński, Tomasz; Lorys, Krzysztof, Church-Rosser languages vs. UCFL., 147-158 [Zbl 1056.68095]
Bala, Sebastian, Intersection of regular languages and star hierarchy, 159-169 [Zbl 1056.68093]
Lombardy, Sylvain, On the construction of reversible automata for reversible languages, 170-182 [Zbl 1056.68097]
Elmasry, Amr, Priority queues, pairing, and adaptive sorting, 183-194 [Zbl 1056.68515]
Bender, Michael A.; Cole, Richard; Raman, Rajeev, Exponential structures for efficient cache-oblivious algorithms, 195-207 [Zbl 1056.68511]
Impagliazzo, Russell; Segerlind, Nathan, Bounded-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations (extended abstract)., 208-219 [Zbl 1056.03504]
Esteban, Juan Luis; Galesi, Nicola; Messner, Jochen, On the complexity of resolution with bounded conjunctions (extended abstract)., 220-231 [Zbl 1056.03503]
Kiayias, Aggelos; Yung, Moti, Cryptographic hardness based on the decoding of Reed-Solomon codes, 232-243 [Zbl 1062.94039]
Ishai, Yuval; Kushilevitz, Eyal, Perfect constant-round secure computation via perfect randomizing polynomials, 244-256 [Zbl 1056.68088]
Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V., Exponential lower bound for static semi-algebraic proofs, 257-268 [Zbl 1056.03037]
Jakoby, Andreas; Liskiewicz, Maciej, Paths problems in symmetric logarithmic space, 269-280 [Zbl 1056.68108]
Damaschke, Peter, Scheduling search procedures, 281-292 [Zbl 1056.68507]
Iwama, Kazuo; Taketomi, Shiro, Removable online knapsack problems, 293-305 [Zbl 1056.68588]
Epstein, Leah; Seiden, Steve; van Stee, Rob, New bounds for variable-sized and resource augmented online bin packing, 306-317 [Zbl 1056.68586]
Ollinger, Nicolas, The quest for small universal cellular automata, 318-329 [Zbl 1056.68104]
Papazian, Christophe; Rémila, Eric, Hyperbolic recognition by graph automata, 330-342 [Zbl 1056.68098]
Ablayev, Farid; Moore, Cristopher; Pollett, Christopher, Quantum and stochastic branching programs of bounded width (Track A)., 343-354 [Zbl 1056.68085]
Gargano, Luisa; Hell, Pavol; Stacho, Ladislav; Vaccaro, Ugo, Spanning trees with bounded number of branch vertices, 355-365 [Zbl 1056.68587]
Beier, René; Sanders, Peter; Sivadasan, Naveen, Energy optimal routing in radio networks using geometric data structures, 366-376 [Zbl 1056.68501]
Christersson, Malin; Gasieniec, Leszek; Lingas, Andrzej, Gossiping with bounded size messages in ad hoc radio networks (extended abstract)., 377-389 [Zbl 1056.68502]
Merkle, Wolfgang, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, 390-400 [Zbl 1056.68090]
Hearn, Robert A.; Demaine, Erik D., The nondeterministic constraint logic model of computation: Reductions and applications, 401-413 [Zbl 1056.68086]
Dalmau, Víctor, Constraint satisfaction problems in non-deterministic logarithmic space, 414-425 [Zbl 1056.68130]
Brodal, Gerth Stølting; Fagerberg, Rolf, Cache oblivious distribution sweeping, 426-438 [Zbl 1056.68543]
Östlin, Anna; Pagh, Rasmus, One-probe search, 439-450 [Zbl 1056.68514]
Charikar, Moses; Indyk, Piotr; Panigrahy, Rina, New algorithms for subset query, partial match, orthogonal range searching, and related problems, 451-462 [Zbl 1056.68512]
Martin, Keye; Mislove, Michael; Worrell, James, Measuring the probabilistic powerdomain, 463-475 [Zbl 1056.68100]
Ong, C.-H. L.; Di Gianantonio, P., Games characterizing Levy-Longo trees., 476-487 [Zbl 1056.68101]
Bauer, Andrej; Escardó, Martín Hötzel; Simpson, Alex, Comparing functional paradigms for exact real-number computation, 488-500 [Zbl 1056.68057]
Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles, Random sampling from Boltzmann principles (extended abstract)., 501-513 [Zbl 1056.68549]
Duch, Amalia; Martínez, Conrado, On the average performance of orthogonal range search in multidimensional data structures, 514-524 [Zbl 1056.68513]
Kick, Marco, Bialgebraic modelling of timed processes, 525-536 [Zbl 1056.68105]
van Breugel, Franck; Shalit, Steven; Worrell, James, Testing labelled Markov processes, 537-548 [Zbl 1057.68074]
Hitchcock, John M.; Lutz, Jack H., Why computational complexity requires stricter martingales, 549-560 [Zbl 1057.68039]
Hitchcock, John M., Correspondence principles for effective dimensions, 561-571 [Zbl 1057.68038]
Meseguer, José; Rosu, Grigore, A total approach to partial algebraic specification, 572-584 [Zbl 1057.68064]
Lohrey, Markus; D’Argenio, Pedro R.; Hermanns, Holger, Axiomatising divergence, 585-596 [Zbl 1057.68069]
Cardelli, Luca; Gardner, Philippa; Ghelli, Giorgio, A spatial logic for querying graphs, 597-610 [Zbl 1057.68606]
Radzik, Tomasz, Improving time bounds on maximum generalised flow computations by contracting the network, 611-622 [Zbl 1057.90501]
Berman, Piotr; Karpinski, Marek, Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION, 623-632 [Zbl 1057.68646]
Demetrescu, Camil; Italiano, Giuseppe F., Improved bounds and new trade-offs for dynamic all pairs shortest paths, 633-643 [Zbl 1057.68648]
Henzinger, Thomas A.; Krishnan, Sriram C.; Kupferman, Orna; Mang, Freddy Y. C., Synthesis of uninitialized systems, 644-656 [Zbl 1057.68060]
Genest, Blaise; Muscholl, Anca; Seidl, Helmut; Zeitoun, Marc, Infinite-state high-level MSCs: Model-checking and realizability (extended abstract), 657-668 [Zbl 1057.68625]
Wich, Klaus, Universal inherence of cycle-free context-free ambiguity functions, 669-680 [Zbl 1057.68053]
Guha, Sudipto; Indyk, Piotr; Muthukrishnan, S.; Strauss, Martin J., Histogramming data streams with fast per-item processing, 681-692 [Zbl 1064.94515]
Charikar, Moses; Chen, Kevin; Farach-Colton, Martin, Finding frequent items in data streams, 693-703 [Zbl 1057.68600]
Cachat, Thierry, Symbolic strategy synthesis for games on pushdown graphs, 704-715 [Zbl 1057.68046]
Srba, Jiří, Strong bisimilarity and regularity of basic process algebra is PSPACE-hard, 716-727 [Zbl 1057.68071]
Brodal, Gerth Stølting; Lyngsø, Rune B.; Östlin, Anna; Pedersen, Christian N. S., Solving the string statistics problem in time \(\mathcal{O}(n\log n)\), 728-739 [Zbl 1057.68599]
Deng, Xiaotie; Li, Guojun; Li, Zimao; Ma, Bin; Wang, Lusheng, A PTAS for distinguishing (sub)string selection, 740-751 [Zbl 1057.68134]
Kuske, Dietrich; Lohrey, Markus, On the theory of one-step rewriting in trace monoids, 752-763 [Zbl 1057.68045]
Bielecki, Michał; Hidders, Jan; Paredaens, Jan; Tyszkiewicz, Jerzy; Van den Bussche, Jan, Navigating with a browser, 764-775 [Zbl 1057.68729]
Kumar, V. S. Anil; Marathe, Madhav V., Improved results for Stackelberg scheduling strategies, 776-787 [Zbl 1057.90018]
Adamy, Udo; Ambuehl, Christoph; Anand, R. Sai; Erlebach, Thomas, Call control in rings, 788-799 [Zbl 1057.68506]
Chrobak, Marek; Epstein, Leah; Noga, John; Sgall, Jiří; van Stee, Rob; Tichý, Tomáš; Vakhania, Nodari, Preemptive scheduling in overloaded systems, 800-811 [Zbl 1057.68542]
Karhumäki, J.; Lisovik, L. P., The equivalence problem of finite substitutions on \(ab^*c \), with applications, 812-820 [Zbl 1057.68048]
Stirling, Colin, Deciding DPDA equivalence is primitive recursive, 821-832 [Zbl 1057.68052]
Bojańczyk, Mikołaj, Two-way alternating automata and finite models, 833-844 [Zbl 1057.03029]
Berman, Piotr; Karpinski, Marek; Nekrich, Yakov, Approximating Huffman codes in parallel, 845-855 [Zbl 1057.68743]
Fantozzi, Carlo; Pietracaprina, Andrea; Pucci, Geppino, Seamless integration of parallelism and memory hierarchy (extended abstract), 856-867 [Zbl 1057.68617]
Nisan, Noam, The communication complexity of approximate set packing and covering, 868-875 [Zbl 1057.68645]
Doerr, Benjamin, Antirandomizing the wrong game, 876-887 [Zbl 1059.91013]
Akcoglu, Karhan; Drineas, Petros; Kao, Ming-Yang, Fast universalization of investment strategies with provably good relative returns, 888-900 [Zbl 1057.91038]
Adler, Micah; Räcke, Harald; Sivadasan, Naveen; Sohler, Christian; Vöcking, Berthold, Randomized pursuit-evasion in graphs, 901-912 [Zbl 1057.91015]
Wells, J. B., The essence of principal typings, 913-925 [Zbl 1057.03023]
Adsul, Bharat; Sohoni, Milind, Complete and tractable local linear time temporal logics over traces, 926-937 [Zbl 1057.68055]
Gastin, Paul; Mukund, Madhavan, An elementary expressively complete temporal logic for Mazurkiewicz traces, 938-949 [Zbl 1057.68058]
Brattka, Vasco, Random numbers and an incomplete immune recursive set, 950-961 [Zbl 1057.03052]
Hertling, Peter, A Banach-Mazur computable but not Markov computable function on the computable real numbers, 962-972 [Zbl 1057.03054]
Czumaj, Artur; Lingas, Andrzej; Zhao, Hairong, Polynomial-time approximation schemes for the Euclidean survivable network design problem, 973-984 [Zbl 1057.90053]
Björklund, Andreas; Husfeldt, Thore, Finding a path of superlogarithmic length, 985-992 [Zbl 1057.68647]
Uehara, Ryuhei, Linear time algorithms on chordal bipartite and strongly chordal graphs, 993-1004 [Zbl 1057.68654]
Holmerin, Jonas, Improved inapproximability results for vertex cover on \(k\)-uniform hypergraphs, 1005-1016 [Zbl 1057.68079]
Kohayakawa, Yoshiharu; Nagle, Brendan; Rödl, Vojtěch, Efficient testing of hypergraphs (extended abstract), 1017-1028 [Zbl 1057.68649]
Wu, Xiaodong; Chen, Danny Z., Optimal net surface problems with applications, 1029-1042 [Zbl 1057.68723]
Bonichon, Nicolas; Le Saëc, Bertrand; Mosbah, Mohamed, Wagner’s theorem on realizers, 1043-1053 [Zbl 1058.05057]
Liberatore, Vincenzo, Circular arrangements, 1054-1065 [Zbl 1057.68009]

MSC:
00B25 Proceedings of conferences of miscellaneous specific interest
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
PDF BibTeX XML Cite