Automata, languages and programming. 22nd international colloquium, ICALP '95, Szeged, Hungary, July 10--14, 1995. Proceedings
The articles of this volume will be reviewed individually. For the preceding colloquium see [Zbl 0844.00024]. Indexed articles: \textit{Ehrenfeucht, A.; Harju, T.; Rozenberg, G.}, Theory of 2-structures, 1-14 [Zbl 1412.68168] \textit{Diekert, Volker; Gastin, Paul}, A domain for concurrent termination a generalization of Mazurkiewicz traces (extended abstract), 15-26 [Zbl 1412.68150] \textit{Ésik, Zoltán; Bertol, Michael}, Nonfinite axiomatizability of the equational theory of shuffle, 27-38 [Zbl 1412.68141] \textit{Kuich, Werner}, The algebraic equivalent of AFL theory, 39-50 [Zbl 1412.68143] \textit{Culik, Karel; Kari, Jarkko}, Finite state transformations of images, 51-62 [Zbl 1412.68125] \textit{Lipponen, Marjo}, Post correspondence problem: words possible as primitive solutions, 63-74 [Zbl 1415.03048] \textit{Métivier, Yves; Richomme, Gwénaël; Wacrenier, Pierre-André}, Computing the closure of sets of words under partial commutations, 75-86 [Zbl 1412.68133] \textit{Bodlaender, Hans L.; de Fluiter, Babette}, Intervalizing \(k\)-colored graphs, 87-98 [Zbl 1412.68162] \textit{Chen, Zhi-Zhong}, NC algorithms for finding a maximal set of paths with application to compressing strings, 99-110 [Zbl 1412.68166] \textit{Giancarlo, Raffaele; Grossi, Roberto}, On the construction of classes of suffix trees for square matrices: algorithms and applications, 111-122 [Zbl 1412.68050] \textit{Parra, Andreas; Scheffler, Petra}, How to use the minimal separators of a graph for its chordal triangulation, 123-134 [Zbl 1412.68171] \textit{Bermond, J.-C.; Gargano, L.; Rescigno, A. A.; Vaccaro, U.}, Fast gossiping by short messages, 135-146 [Zbl 1412.68013] \textit{Bao, Feng; Igarashi, Yoshihide}, Break finite automata public key cryptosystem, 147-158 [Zbl 1415.94407] \textit{Nikoletseas, S.; Reif, J.; Spirakis, P.; Yung, M.}, Stochastic graphs have short memory: fully dynamic connectivity in poly-log expected time, 159-170 [Zbl 1412.68170] \textit{Blundo, Carlo; De Santis, Alfredo; Persiano, Giuseppe; Vaccaro, Ugo}, On the number of random bits in totally private computation, 171-182 [Zbl 1412.68062] \textit{Freivalds, Rūsiņš; Karpinski, Marek}, Lower time bounds for randomized computation, 183-195 [Zbl 1412.68063] \textit{Köbler, Johannes; Watanabe, Osamu}, New collapse consequences of NP having small circuits, 196-207 [Zbl 1412.68067] \textit{Balcázar, José L.}, The complexity of searching succinctly represented graphs, 208-219 [Zbl 1412.68077] \textit{Bauernöppel, Frank; Kranakis, Evangelos; Krizanc, Danny; Maheshwari, Anil; Noy, Marc; Sack, Jörg-Rüdiger; Urrutia, Jorge}, Optimal shooting: characterizations and applications, 220-231 [Zbl 1412.68286] \textit{Auletta, Vincenzo; Parente, Domenico; Persiano, Giuseppe}, Placing resources in a tree: dynamic and static algorithms, 232-243 [Zbl 1412.68076] \textit{Chaudhuri, Shiva; Zaroliagis, Christos D.}, Shortest path queries in digraphs of small treewidth, 244-255 [Zbl 1412.68164] \textit{Golin, M. J.; Rote, Günter}, A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs, 256-267 [Zbl 1412.68083] \textit{Bodlaender, Hans L.; Hagerup, Torben}, Parallel algorithms with optimal speedup for bounded treewidth, 268-279 [Zbl 1412.68292] \textit{Rauch Henzinger, Monika}, Approximating minimum cuts under insertions, 280-291 [Zbl 1412.68173] \textit{Corneil, Derek G.; Olariu, Stephan; Stewart, Lorna}, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, 292-302 [Zbl 1415.05130] \textit{Leonardi, Stefano; Marchetti-Spaccamela, Alberto}, On-line resource management with applications to routing and scheduling, 303-314 [Zbl 1412.68301] \textit{Petersen, H.}, Alternation in simple devices, 315-323 [Zbl 1412.68134] \textit{Henzinger, Thomas A.}, Hybrid automata with finite bisimulations, 324-335 [Zbl 1412.68130] \textit{Lopez, Luis-Miguel; Narbel, Philippe}, Generalized Sturmian languages, 336-347 [Zbl 1412.68144] \textit{Pin, Jean-Eric; Weil, Pascal}, Polynomial closure and unambiguous product, 348-359 [Zbl 1412.68145] \textit{Ben-Amram, Amir M.; Galil, Zvi}, Lower bounds on algebraic random access machines, 360-371 [Zbl 1412.68057] \textit{Pietracaprina, Andrea; Pucci, Geppino}, Improved deterministic PRAM simulation on the mesh, 372-383 [Zbl 1412.68012] \textit{Ambos-Spies, Klaus}, On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability, 384-392 [Zbl 1412.68074] \textit{Fenner, Stephen A.; Lutz, Jack H.; Mayordomo, Elvira}, Weakly useful sequences, 393-404 [Zbl 1412.68092] \textit{Schwentick, Thomas}, Graph connectivity, monadic NP and built-in relations of moderate degree, 405-416 [Zbl 1412.68068] \textit{Henzinger, Thomas A.; Kopke, Peter W.; Wong-Toi, Howard}, The expressive power of clocks, 417-428 [Zbl 1412.68131] \textit{Păun, Gheorghe}, Grammar systems: a grammatical approach to distribution and cooperation, 429-443 [Zbl 1412.68114] \textit{Harju, T.; Karhumäki, J.; Plandowski, W.}, Compactness of systems of equations in semigroups, 444-454 [Zbl 1434.20040] \textit{Ďuriš, Pavol; Galil, Zvi}, Sensing versus nonsensing automata, 455-463 [Zbl 1412.68127] \textit{Bozanis, Panayiotis; Kitsios, Nectarios; Makris, Christos; Tsakalidis, Athanasios}, New upper bounds for generalized intersection searching problems, 464-474 [Zbl 1412.68287] \textit{Becker, Bernd; Drechsler, Rolf; Theobald, Michael}, OKFDDs versus OBDDs and OFDDs, 475-486 [Zbl 1412.68046] \textit{Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J.; Hunt, H. B. III}, Bicriteria network design problems, 487-498 [Zbl 1415.90138] \textit{Lê, Ngọc-Minh}, On determining optimal strategies in pursuit games in the plane, 499-510 [Zbl 1412.68280] \textit{Rubio, Albert}, Extension orderings, 511-522 [Zbl 1412.68117] \textit{Greco, Sergio; Saccà, Domenico; Zaniolo, Carlo}, The pushdown method to optimize chain logic programs, 523-534 [Zbl 1412.68031] \textit{Andersen, Jørgen H.; Kristoffersen, Kåre J.; Larsen, Kim G.; Niedermann, Jesper}, Automatic synthesis of real time systems, 535-546 [Zbl 1412.68136] \textit{Blum, Manuel; Codenotti, Bruno; Gemmell, Peter; Shahoumian, Troy}, Self-correcting for function fields of finite transcendental degree, 547-557 [Zbl 1412.68303] \textit{Fortnow, Lance; Freivalds, Rūsiņš; Gasarch, William I.; Kummer, Martin; Kurtz, Stuart A.; Smith, Carl; Stephan, Frank}, Measure, category and learning theory, 558-569 [Zbl 1412.68093] \textit{Cosnard, Michel; Goles, Eric}, A characterization of the existence of energies for neural networks, 570-580 [Zbl 1412.68180] \textit{Jürgensen, H.; Konstantinidis, S.}, Variable-length codes for error correction, 581-592 [Zbl 1415.94396] \textit{Khuller, Samir; Rivlin, Ehud; Rosenfeld, Azriel}, Graphbots: mobility in discrete spaces, 593-604 [Zbl 1412.68279] \textit{Best, Eike; Koutny, Maciej}, Solving recursive net equations, 605-623 [Zbl 1412.68147] \textit{Dawar, Anuj; Hella, Lauri; Kolaitis, Phokion G.}, Implicit definability and infinitary logic in finite model theory (extended abstract), 624-635 [Zbl 1415.03041] \textit{Vogler, Walter}, The limit of \(\operatorname{split}_n\)-language equivalence, 636-647 [Zbl 1412.68157] \textit{Natarajan, V.; Cleaveland, Rance}, Divergence and fair testing, 648-659 [Zbl 1412.68155] \textit{Degano, Pierpaolo; Priami, Corrado}, Causality for mobile processes, 660-671 [Zbl 1412.68149] \textit{Sangiorgi, Davide}, Internal mobility and agent-passing calculi, 672-683 [Zbl 1412.68156]
scientific article; zbMATH DE number 780861