Automata, languages and programming. 20th international colloquium, ICALP 93, Lund, Sweden, July 5--9, 1993. Proceedings (Q1309676)

The articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1369.68031]. Further articles of this colloquium have been published in Nord. J. Comput. 1, No. 3 (1994). Indexed articles: \textit{Blum, Manuel}, Program result checking: a new approach to making programs more reliable, 1-14 [Zbl 1418.68089] \textit{Andersson, Arne; Mattsson, Christer}, Dynamic interpolation search in \(o(\log\log n)\) time, 15-27 [Zbl 1418.68071] \textit{Frederickson, Greg N.}, Searching among intervals and compact routing tables, 28-39 [Zbl 1418.68073] \textit{Lund, Carsten; Yannakakis, Mihalis}, The approximation of maximum subgraph problems, 40-51 [Zbl 1422.68087] \textit{Kann, Viggo}, Polynomially bounded minimization problems which are hard to approximate, 52-63 [Zbl 1422.68120] \textit{Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis}, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, 64-75 [Zbl 1418.68244] \textit{Marathe, M. V.; Hunt, H. B. III; Ravi, S. S.}, The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications, 76-87 [Zbl 1422.68128] \textit{Czumaj, Artur; Gibbons, Alan}, Problems on pairs of trees and the four colour problem of planar graphs (extended abstract), 88-101 [Zbl 1418.68101] \textit{Kalyanasundaram, Bala; Pruhs, Kirk R.}, Constructing competitive tours from local information, 102-113 [Zbl 1422.68190] \textit{Bodlaender, Hans; Kloks, Ton; Kratsch, Dieter}, Treewidth and pathwidth of permutation graphs, 114-125 [Zbl 1418.68162] \textit{Jaromczyk, Jerzy W.; Świcatek, Grzegorz}, A theory of even functionals and their algorithmic applications, 126-136 [Zbl 1422.68118] \textit{Flajolet, Philippe; Golin, Mordecai}, Exact asymptotics of divide-and-conquer recurrences, 137-149 [Zbl 1418.68252] \textit{Kozen, Dexter; Zaks, Shmuel}, Optimal bounds for the change-making problem, 150-161 [Zbl 1422.68123] \textit{Reif, John H.; Tate, Stephen R.}, The complexity of \(n\)-body simulation, 162-176 [Zbl 1422.68139] \textit{Dillencourt, Michael B.; Smith, Warren D.}, A simple method for resolving degeneracies in Delaunay triangulations, 177-188 [Zbl 1418.68226] \textit{Hemachandra, Lane A.}, Fault-tolerance and complexity (extended abstract), 189-202 [Zbl 1418.68075] \textit{Yamamoto, Hiroaki}, Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines, 203-214 [Zbl 1420.68089] \textit{Orponen, Pekka}, On the computational power of discrete Hopfield nets, 215-226 [Zbl 1422.68072] \textit{Karpinski, Marek; Verbeek, Rutger}, On randomized versus deterministic computation, 227-240 [Zbl 1420.68091] \textit{Ablayev, Farid}, Lower bounds for one-way probabilistic communication complexity, 241-252 [Zbl 1418.68097] \textit{Hagerup, Torben; Mehlhorn, Kurt; Munro, J. Ian}, Maintaining discrete probability distributions optimally, 253-264 [Zbl 1418.68158] \textit{Franklin, Matthew; Yung, Moti}, Secure and efficient off-line digital money (extended abstract), 265-276 [Zbl 1418.68081] \textit{Juedes, David W.; Lathrop, James I.; Lutz, Jack H.}, Computational depth and reducibility, 277-288 [Zbl 1422.68145] \textit{Baliga, Ganesh; Case, John}, Learnability: admissible, co-finite, and hypersimple languages, 289-300 [Zbl 1418.68109] \textit{Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng}, Inclusion is undecidable for pattern languages, 301-312 [Zbl 1422.68152] \textit{Ibarra, Oscar H.; Jiang, Tao; Tran, Nicholas; Wang, Hui}, New decidability results concerning two-way counter machines and applications, 313-324 [Zbl 1422.68150] \textit{Michaux, Christian; Villemaire, Roger}, Cobham's theorem seen through Büchi's theorem, 325-334 [Zbl 1422.68156] \textit{Ebinger, Werner; Muscholl, Anca}, Logical definability on infinite traces, 335-346 [Zbl 1418.68116] \textit{Wilke, Thomas}, Algebras for classifying regular tree languages and an application to frontier testability, 347-358 [Zbl 1422.68165] \textit{Gupta, Arvind}, Finite automata as characterizations of minor closed tree families (extended abstract), 359-370 [Zbl 1418.68120] \textit{Dolev, Danny; Malki, Dalia}, On distributed algorithms in a broadcast domain, 371-387 [Zbl 1418.68016] \textit{Chlebus, Bogdan S.; Diks, Krzysztof; Pelc, Andrzej}, Sparse networks supporting efficient reliable broadcasting, 388-397 [Zbl 1418.68009] \textit{Meyer auf der Heide, Friedhelm; Oesterdiekhoff, Brigitte; Wanka, Rolf}, Strongly adaptive token distribution, 398-409 [Zbl 1422.68267] \textit{Schönhage, Arnold}, Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic, 410-417 [Zbl 1422.68330] \textit{Kirousis, Lefteris M.}, Fast parallel constraint satisfaction, 418-429 [Zbl 1422.68122] \textit{Simon, Imre}, The product of rational languages, 430-444 [Zbl 1422.68160] \textit{Ochmański, Edward; Wacrenier, Pierre-André}, On regular compatibility of semi-commutations, 445-456 [Zbl 1422.68158] \textit{Dumas, Ph.}, Algebraic aspects of \(\mathrm{B}\)-regular series, 457-468 [Zbl 1418.68128] \textit{Cohen, David M.; Fredman, Michael L.}, Products of finite state machines with full coverage, 469-477 [Zbl 1418.68115] \textit{Sénizergues, Géraud}, An effective version of Stallings' theorem in the case of context-free groups, 478-495 [Zbl 1422.20010] \textit{Lepistö, Arto}, On the power of periodic iteration of morphisms, 496-506 [Zbl 1422.68155] \textit{Mignosi, Filippo; Séébold, Patrice}, If a D0L language is \(k\)-power free then it is circular, 507-518 [Zbl 1422.68157] \textit{Jategaonkar, Lalita; Meyer, Albert}, Deciding true concurrency equivalences on finite safe nets (preliminary report), 519-531 [Zbl 1422.68170] \textit{Vogler, Walter}, Timed testing of concurrent systems, 532-543 [Zbl 1422.68175] \textit{Havelund, Klaus; Larsen, Kim G.}, The fork calculus, 544-557 [Zbl 1418.68142] \textit{Inverardi, Paula; Priami, Corrado; Yankelevich, Daniel}, Extended transition systems for parametric bisimulation, 558-569 [Zbl 1422.68169] \textit{Brown, Carolyn; Gurr, Doug}, Temporal logic and categories of Petri nets, 570-581 [Zbl 1418.68135] \textit{Lodaya, Kamal; Ramanujam, R.; Thiagarajan, P. S.}, Decidability of a partial order based temporal logic, 582-592 [Zbl 1422.03027] \textit{Hungar, Hardi; Steffen, Bernhard}, Local model checking for context-free processes, 593-605 [Zbl 1422.68163] \textit{Abiteboul, Serge; Vianu, Victor}, Computing on structures, 606-620 [Zbl 1418.68087] \textit{Contejean, Evelyne}, A partial solution for \(D\)-unification based on a reduction to AC1-unification, 621-632 [Zbl 1422.03016] \textit{Codish, Michael; Falaschi, Moreno; Marriott, Kim; Winsborough, William}, Efficient analysis of concurrent constraint logic programs, 633-644 [Zbl 1418.68052] \textit{Di Cosmo, Roberto; Kesner, Delia}, A confluent reduction for the extensional typed \(\lambda\)-calculus with pairs, sums, recursion and terminal object, 645-656 [Zbl 1422.03022] \textit{Barbanera, Franco; Fernández, Maribel}, Modularity of termination and confluence in combinations of rewrite systems with \(\lambda_\omega\), 657-668 [Zbl 1418.68110] \textit{Bracho, Felipe; Droste, Manfred}, From domains to automata with concurrency, 669-681 [Zbl 1418.68134] \textit{Kanneganti, Ramarao; Cartwright, Robert}, What is a universal higher-order programming language?, 682-695 [Zbl 1422.68021]