Automata, languages and programming. 21st international colloquium, ICALP '94, Jerusalem, Israel, July 11--14, 1994. Proceedings (Q1327702)

The articles of this volume will be reviewed individually. For the preceding colloquium see [Zbl 0814.00020]. Indexed articles: \textit{Pudlák, Pavel}, Unexpected upper bounds on the complexity of some communication games, 1-10 [Zbl 1422.68134] \textit{Fernau, Henning; Staiger, Ludwig}, Valuations and unambiguity of languages, with applications to fractal geometry, 11-22 [Zbl 1418.68117] \textit{Siegelmann, Hava T.}, On the computational power of probabilistic and faulty neural networks, 23-34 [Zbl 1422.68074] \textit{Čerāns, Kārlis}, Deciding properties of integral relational automata, 35-46 [Zbl 1418.68126] \textit{Aumann, Yonatan; Bar-Ilan, Judit; Feige, Uriel}, On the cost of recomputing: tight bounds on pebbling with faults, 47-58 [Zbl 1418.68100] \textit{Asarin, Eugene; Maler, Oded}, On some relations between dynamical systems and transition systems, 59-72 [Zbl 1418.68088] \textit{Globerman, Noa; Harel, David}, Complexity results for multi-pebble automata and their logics, 73-82 [Zbl 1418.68118] \textit{Kanellakis, Paris C.; Hillebrand, Gerd G.; Mairson, Harry G.}, An analysis of the Core-ML language: expressive power and type reconstruction, 83-105 [Zbl 1422.68020] \textit{Gyssens, Marc; Van den Bussche, Jan; Van Gucht, Dirk}, Expressiveness of efficient semi-deterministic choice constructs, 106-117 [Zbl 1418.68074] \textit{Grädel, Erich; Gurevich, Yuri}, Tailoring recursion for complexity, 118-129 [Zbl 1418.68096] \textit{Klarlund, Nils; Mukund, Madhavan; Sohoni, Milind}, Determinizing asynchronous automata, 130-141 [Zbl 1422.68153] \textit{Muscholl, Anca}, On the complementation of Büchi asynchronous cellular automata, 142-153 [Zbl 1422.68166] \textit{Corradini, Flavio; De Nicola, Rocco}, Distribution and locality of concurrent systems, 154-165 [Zbl 1418.68137] \textit{Gawlick, Rainer; Segala, Roberto; Søgaard-Andersen, Jørgen; Lynch, Nancy}, Liveness in timed and untimed systems, 166-177 [Zbl 1418.68139] \textit{Sánchez-Couso, José-Ramón; Fernández-Camacho, María-Inés}, Average-case analysis of pattern-matching in trees under the bst probability model, 178-190 [Zbl 1422.68142] \textit{Jiang, Tao; Li, Ming}, On the approximation of shortest common supersequences and longest common subsequences, 191-202 [Zbl 1422.68119] \textit{Hariharan, Ramesh; Muthukrishnan, S.}, Optimal parallel algorithms for prefix matching, 203-214 [Zbl 1418.68249] \textit{Amir, Amihood; Benson, Gary; Farach, Martin}, Optimal two-dimensional compressed matching, 215-226 [Zbl 1418.68084] \textit{Italiano, Giuseppe F.; Ramaswami, Rajiv}, Maintaining spanning trees of small diameter, 227-238 [Zbl 1422.68189] \textit{Gil, Joseph; Matias, Yossi}, Simple fast parallel hashing, 239-250 [Zbl 1418.68236] \textit{Przytycka, Teresa M.; Larmore, Lawrence L.}, The optimal alphabetic tree problem revisited, 251-262 [Zbl 1422.68133] \textit{Buhrman, Harry; Torenvliet, Leen}, On the cutting edge of relativization: the resource bounded injury method, 263-273 [Zbl 1420.68090] \textit{Birget, J.-C.; Margolis, S.; Meakin, J.; Weil, P.}, PSPACE-completeness of certain algorithmic problems on the subgroups of free groups, 274-285 [Zbl 1418.68098] \textit{Hennessy, M.}, Higher-order processes and their models, 286-303 [Zbl 1418.68143] \textit{Vergauwen, B.; Lewi, J.}, Efficient local correctness checking for single and alternating Boolean equation systems, 304-315 [Zbl 1422.68174] \textit{Abdulla, Parosh Aziz; Jonsson, Bengt}, Undecidable verification problems for programs with unreliable channels, 316-327 [Zbl 1418.68123] \textit{Fix, Limor; Schneider, Fred B.}, Reasoning about programs by exploiting the environment, 328-339 [Zbl 1418.68054] \textit{Braüner, Torben}, A model of intuitionistic affine logic from stable domain theory, 340-351 [Zbl 1422.03134] \textit{Plotkin, Gordon; Winskel, Glynn}, Bistructures, bidomains and linear logic, 352-363 [Zbl 1422.03130] \textit{Aziz, Adnan; Singhal, Vigyan; Balarin, Felice; Brayton, Robert K.; Sangiovanni-Vincentelli, Alberto L.}, Equivalences for fair Kripke structures, 364-375 [Zbl 1418.68125] \textit{van Breugel, Franck}, Generalizing finiteness conditions of labelled transition systems, 376-387 [Zbl 1422.68173] \textit{Droste, Manfred}, A Kleene theorem for recognizable languages over concurrency monoids, 388-399 [Zbl 1418.68138] \textit{Seidl, Helmut}, Least solutions of equations over \(\mathcal{N}\), 400-411 [Zbl 1422.68036] \textit{Hotz, Günter; Pitsch, Gisela}, Fast uniform analysis of coupled-context-free languages, 412-423 [Zbl 1422.68149] \textit{Pin, Jean-Eric}, Polynomial closure of group languages and open sets of the Hall topology, 424-435 [Zbl 1422.68159] \textit{Caron, Anne-Cécile; Comon, Hubert; Coquidé, Jean-Luc; Dauchet, Max; Jacquemard, Florent}, Pumping, cleaning and symbolic constraints solving, 436-449 [Zbl 1418.68114] \textit{Hintermeier, Claus; Kirchner, Claude; Kirchner, Hélène}, Dynamically-typed computations for order-sorted equational presentations, 450-461 [Zbl 1418.68057] \textit{Di Cosmo, Roberto; Kesner, Delia}, Combining first order algebraic rewriting systems, recursion and extensional lambda calculi, 462-472 [Zbl 1418.68112] \textit{Upfal, Eli}, On the theory of interconnection networks for parallel computers, 473-486 [Zbl 1422.68009] \textit{Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis}, Multiway cuts in directed and node weighted graphs (extended abstract), 487-498 [Zbl 1418.68168] \textit{Feige, Uriel}, A fast randomized LOGSPACE algorithm for graph connectivity, 499-507 [Zbl 1418.68167] \textit{Nikoletseas, S.; Palem, K.; Spirakis, P.; Yung, M.}, Short vertex disjoint paths and multiconnectivity in random graphs: reliable network computing, 508-519 [Zbl 1422.68192] \textit{Lagergren, Jens}, The size of an intertwine, 520-531 [Zbl 1422.68124] \textit{Yuster, Raphael; Zwick, Uri}, Finding even cycles even faster, 532-543 [Zbl 1422.05098] \textit{Höfting, F.; Wanke, E.}, Polynomial time analysis of toroidal periodic graphs, 544-555 [Zbl 1422.68114] \textit{Bonizzoni, P.}, A tight lower bound for primitivity in \(k\)-structures, 556-567 [Zbl 1418.68163] \textit{Blundo, Carlo; De Santis, Alfredo; Vaccaro, Ugo}, Randomness in distribution protocols, 568-579 [Zbl 1418.68079] \textit{Freivalds, Rusins; Karpinski, Marek}, Lower space bounds for randomized computation, 580-592 [Zbl 1418.68094] \textit{Jakoby, Andreas; Schindelhauer, Christian; Reischuk, Rüdiger; Weis, Stephan}, The average case complexity of the parallel prefix problem, 593-604 [Zbl 1422.68117] \textit{Golin, Mordecai J.; Young, Neal}, Prefix codes: equiprobable words, unequal letter costs, 605-617 [Zbl 1418.68119] \textit{Plaxton, C. Greg; Suel, Torsten}, A super-logarithmic lower bound for hypercubic sorting networks, 618-629 [Zbl 1422.68092] \textit{Mei, Aohan; Igarashi, Yoshihide}, Efficient strategies for robot navigation in unknown environment, 630-641 [Zbl 1422.68223]