Mathematical foundations of computer science 1997. 22nd international symposium, MFCS '97, Bratislava, Slovakia, August 25--29, 1997. Proceedings (Q1294951)

The articles of mathematical interest will be reviewed individually. The 23rd international symposium 1998 has been indicated (see Zbl 0895.00049). Indexed articles: \textit{Babai, László}, Communication complexity, 5-18 [Zbl 0941.68088] \textit{Bodlaender, Hans L.}, Treewidth: Algorithmic techniques and results, 19-36 [Zbl 0941.05057] \textit{Dwork, Cynthia}, Positive applications of lattices to cryptography, 44-51 [Zbl 0972.94034] \textit{Ferrari, GianLuigi; Montanari, Ugo}, A tile-based coordination view of asynchronous \(\pi\)-calculus, 52-70 [Zbl 0941.68089] \textit{Hromkovič, Juraj; Schnitger, Georg}, Communication complexity and sequential computation, 71-84 [Zbl 0941.68090] \textit{Krajíček, Jan}, Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus, 85-90 [Zbl 0935.03068] \textit{Liśkiewicz, Maciej; Reischuk, Rüdiger}, Computational limitations of stochastic Turing machines and Arthur-Merlin games with small space bounds, 91-107 [Zbl 0951.68036] \textit{Schöning, Uwe}, Resolution proofs, exponential bounds, and Kolmogorov complexity, 110-116 [Zbl 0976.03063] \textit{Mundhenk, Martin; Goldsmith, Judy; Allender, Eric}, The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes, 129-138 [Zbl 0947.90599] \textit{Bernardinello, Luca; Pomello, Lucia}, A category of transition systems and its relations with orthomodular posets, 139-148 [Zbl 0934.18005] \textit{Bérard, Béatrice; Picaronny, Claudine}, Accepting Zeno words without making time stand still, 149-158 [Zbl 0941.68044] \textit{Bonsangue, Marcello M.; Kok, Joost N.}, Specifying computations using hyper transition systems, 169-178 [Zbl 0941.68081] \textit{Cattaneo, G.; Formenti, E.; Margara, L.; Mazoyer, J.}, A shift-invariant metric on \(S^{\mathbb{Z}}\) inducing a non-trivial topology, 179-188 [Zbl 0941.37006] \textit{Chen, Gang}, Subtyping calculus of construction. (Extended abstract), 189-198 [Zbl 0935.03023] \textit{Choffrut, Christian; Pighizzini, Giovanni}, Distances between languages and reflexivity of relations, 199-208 [Zbl 0941.68071] \textit{Ryl, Isabelle; Roos, Yves; Clerbout, Mireille}, Partial characterization of synchronization languages, 209-218 [Zbl 0941.68072] \textit{Heckel, Reiko; Ehrig, Hartmut; Wolter, Uwe; Corradini, Andrea}, Integrating the specification techniques of graph transformation and temporal logic, 219-228 [Zbl 0951.68055] \textit{Drewes, Frank}, On the generation of trees by hyperedge replacement, 229-238 [Zbl 0941.68066] \textit{Fernau, Henning; Stiebe, Ralf}, Regulation by valences, 239-248 [Zbl 0946.68066] \textit{Fokkink, Wan; van de Pol, Jaco}, Simulation as a correct transformation of rewrite systems, 249-258 [Zbl 0941.68067] \textit{Gavoille, Cyril}, On the dilation of interval routing, 259-268 [Zbl 0941.68097] \textit{Khasidashvili, Zurab; Glauert, John}, Relating conflict-free stable transition and event models. (Extended abstract), 269-278 [Zbl 0942.68061] \textit{Goerdt, Andreas}, The giant component threshold for random regular graphs with edge faults, 279-288 [Zbl 0941.68098] \textit{Heinemann, Bernhard}, A topological generalization of propositional linear time temporal logic, 289-297 [Zbl 0943.03016] \textit{Holzer, Markus}, Multi-head finite automata: Data-independent \textit{versus} data-dependent computations, 299-308 [Zbl 0941.68045] \textit{Iwama, Kazuo}, Complexity of finding short resolution proofs, 309-318 [Zbl 0935.03067] \textit{Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.}, On P versus \(\text{NP}\cap co-\text{NP}\) for decision trees and read-once branching programs, 319-326 [Zbl 0941.68062] \textit{Karner, Georg; Kuich, Werner}, A characterization of abstract families of algebraic power series, 327-336 [Zbl 0938.16034] \textit{Kobayashi, Yuji; Otto, Friedrich}, Repetitiveness of D0L-languages is decidable in polynomial time, 337-346 [Zbl 0946.68085] \textit{Kolpakov, Roman; Kucherov, Gregory}, Minimal letter frequency in \(n\)-th power-free binary words, 347-357 [Zbl 0941.68103] \textit{Korec, Ivan}, Real-time generation of primes by a one-dimensional cellular automaton with 11 states, 358-367 [Zbl 0941.68084] \textit{Manzini, Giovanni; Margara, Luciano}, Invertible linear cellular automata over \({\mathbf Z}_m\): Algorithmic and dynamical aspects, 378-387 [Zbl 0941.68085] \textit{Martin-Vide, Carlos; Miquel-Verges, Joan; Păun, Gheorghe}, Two-level contextual grammars: The internal case, 388-397 [Zbl 0946.68067] \textit{Meer, Klaus}, Counting problems over the reals, 398-407 [Zbl 0946.68057] \textit{Meinel, Christoph; Theobald, Thorsten}, On the influence of the state encoding on OBDD-representations of finite state machines, 408-417 [Zbl 0951.68037] \textit{Meyer, Raphaël; Petit, Antoine}, Decomposition of TrPTL formulas, 418-427 [Zbl 0941.68082] \textit{Mundhenk, Martin}, NP-hard sets have many hard instances, 428-437 [Zbl 0938.03061] \textit{Nickelsen, Arfst}, Deciding verbose languages with linear advice, 438-447 [Zbl 0947.68069] \textit{Petersen, Holger}, Homomorphic images of sentential forms and terminating grammars. (Extended abstract), 448-457 [Zbl 0941.68073] \textit{Plump, Detlef}, Simplification orders for term graph rewriting, 458-467 [Zbl 0941.68068] \textit{Rensink, Arend; Wehrheim, Heike}, Dependency-based action refinement, 468-477 [Zbl 0951.68098] \textit{Savický, P.; Žák, S.}, A hierarchy for \((1,+k)\)-branching programs with respect to \(k\), 478-487 [Zbl 0941.68046] \textit{Vogler, Walter}, Partial order semantics and read arcs, 508-517 [Zbl 0941.68091]