Automata, languages and programming. 26th international colloquium, ICALP `99. Prague, Czech Republic, July 11--15, 1999. Proceedings (Q1295986)

The articles of mathematical interest will be reviewed individually. The preceding colloquium (25th, 1998) has been announced (see Zbl 0893.00039). Indexed articles: \textit{Ajtai, Miklós}, Generating hard instances of the short basis problem, 01-09 [Zbl 0987.94021] \textit{Compton, Kevin J.; Dexter, Scott}, Proof techniques for cryptographic protocols, 25-39 [Zbl 0987.94508] \textit{Cucker, Felipe}, Real computations with fake numbers, 55-73 [Zbl 0944.03030] \textit{Edalat, Abbas; Krznarić, Marko}, Numerical integration with exact real arithmetic, 90-104 [Zbl 0937.65025] \textit{Rozenberg, Grzegorz; Salomaa, Arto}, DNA computing: New ideas and paradigms, 106-118 [Zbl 0939.68040] \textit{Allender, Eric; Ambainis, Andris; Mix Barrington, David A.; Datta, Samir; Huong Lê Thanh}, Bounded depth arithmetic circuits: Counting and closure, 149-158 [Zbl 1020.94543] \textit{Alur, Rajeev; Etessami, Kousha; La Torre, Salvatore; Peled, Doron}, Parametric temporal logic for ``model measuring'', 159-168 [Zbl 0939.03021] \textit{Andreev, Alexander E.; Baskakov, Juri L.; Clementi, Andrea E. F.; Rolim, José D. P.}, Small pseudo-random sets yield hard functions: New tight explicit lower bounds for branching programs, 179-189 [Zbl 0941.68567] \textit{Bednarczyk, Marek A.; Borzyszkowski, Andrzej M.}, General morphisms of Petri nets. (Extended abstract), 190-199 [Zbl 0941.68645] \textit{Bouyer, Patricia; Petit, Antoine}, Decomposition and composition of timed automata, 210-219 [Zbl 0946.68094] \textit{Buhrman, Harry; Jiang, Tao; Li, Ming; Vitányi, Paul}, New applications of the incompressibility method. (Extended abstract), 220-229 [Zbl 0939.68055] \textit{Clote, Peter}, Protein folding, the Levinthal paradox and rapidly mixing Markov chains., 240-249 [Zbl 1037.92016] \textit{Cortier, Veronique; Ganzinger, Harald; Jacquemard, Florent; Veanes, Margus}, Decidable fragments of simultaneous rigid reachability, 250-260 [Zbl 0943.68096] \textit{De Santis, A.; Di Crescenzo, G.; Persiano, G.}, Non-interactive zero-knowledge: A low randomness characterization of NP, 271-280 [Zbl 0943.68073] \textit{Dickhöfer, Martin; Wilke, Thomas}, Timed alternating tree automata: The automata-theoretic solution to the TCTL model checking problem, 281-290 [Zbl 0939.03041] \textit{Dufourd, C.; Jancǎr, P.; Schnoebelen, Ph.}, Boundedness of reset P/T nets, 301-310 [Zbl 0943.68122] \textit{Engelfriet, Joost; Hoogeboom, Hendrik Jan}, Two-way finite state transducers and monadic second-order logic, 311-320 [Zbl 0946.68083] \textit{Frick, Markus; Grohe, Martin}, Deciding first-order properties of locally tree-decomposable graphs, 331-340 [Zbl 0939.03010] \textit{Gottlob, Georg; Leone, Nicola; Scarcello, Francesco}, Computing LOGCFL certificates, 361-371 [Zbl 0941.68580] \textit{Hirshfeld, Yoram; Jerrum, Mark}, Bisimulation equivalence is decidable for normed process algebra. (Extended abstract), 412-421 [Zbl 0941.68574] \textit{Hirshfeld, Yoram; Rabinovich, Alexander}, A framework for decidable metrical logics, 422-432 [Zbl 0939.03023] \textit{Hromkovič, Juraj; Schnitger, Georg}, On the power of Las Vegas. II: Two-way finite automata, 433-442 [Zbl 0939.68071] \textit{Iwama, Kazuo; Manlove, David; Miyazaki, Shuichi; Morita, Yasufumi}, Stable marriage with incomplete lists and ties, 443-452 [Zbl 0948.90155] \textit{Kirsten, Daniel}, A connection between the star problem and the finite power property in trace monoids. (Extended abstract), 473-482 [Zbl 0941.20068] \textit{Kirsten, Daniel; Marcinkowski, Jerzy}, Two techniques in the area of the star problem, 483-492 [Zbl 0941.20069] \textit{Lepistö, A.}, Relations between local and global periodicity of words. (Extended abstract), 534-543 [Zbl 0941.68658] \textit{Miculan, Marino}, Formalizing a lazy substitution proof system for \(\mu\)-calculus in the calculus of inductive constructions, 554-564 [Zbl 0939.03024] \textit{Nichitiu, Codrin; Rémila, Eric}, Leader election by \(d\) dimensional cellular automata, 565-574 [Zbl 0941.68640] \textit{Niedermeier, Rolf; Rossmanith, Peter}, New upper bounds for MaxSat, 575-584 [Zbl 0946.68061] \textit{Olshevsky, Vadim; Pan, Victor Y.}, Polynomial and rational evaluation and interpolation (with structured matrices), 585-594 [Zbl 0937.65010] \textit{Peichl, Timo; Vollmer, Heribert}, Finite automata with generalized acceptance criteria, 605-614 [Zbl 0943.68119] \textit{Power, John; Thielecke, Hayo}, Closed Freyd- and \(\kappa\)-categories, 625-634 [Zbl 0938.03026] \textit{Rutten, J. J. M. M.}, Automata, power series, and coinduction: Taking input derivatives seriously. (Extended abstract), 646-654 [Zbl 0941.68638] \textit{Sénizergues, Géraud}, T(A)=T(B)?, 665-675 [Zbl 0943.68118] \textit{Szegedy, Mario}, Many-valued logics and holographic proofs, 676-686 [Zbl 0938.03022] \textit{Umans, Christopher}, On the complexity and inapproximability of shortest implicant problems, 687-696 [Zbl 0983.94064] \textit{Weihrauch, Klaus; Zhong, Ning}, The wave propagator is Turing computable, 697-706 [Zbl 0945.03092] \textit{Tiskin, A.}, Erratum: Bulk-synchronous parallel multiplication of Boolean matrices, 717-718 [Zbl 0938.65076]