Mathematical foundations of computer science 1995. 20th international symposium, MFCS '95, Prague, Czech Republic, August 28-September 1, 1995. Proceedings (Q1899993)

The articles of this volume will be reviewed individually. The 15th international symposium (1990) has been reviewed (see Zbl 0776.00038). Indexed articles: \textit{Adler, Micah; Byers, John W.; Karp, Richard M.}, Scheduling parallel communication: The \(h\)-relation problem, 1-20 [Zbl 1193.68054] \textit{Arnborg, Stefan}, Decomposable structures, Boolean function representations, and optimization, 21-36 [Zbl 1193.68184] \textit{Flammini, Michele; van Leeuwen, Jan; Marchetti-Spaccamela, Alberto}, The complexity of interval routing on random graphs, 37-49 [Zbl 1193.68189] \textit{Geffert, Viliam}, Bridging across the \(\log (n)\) space frontier, 50-65 [Zbl 1193.68114] \textit{Gottlob, Georg; Leone, Nicola; Veith, Helmut}, Second order logic and the weak exponential hierarchies, 66-81 [Zbl 1193.68115] \textit{Hartmanis, Juris}, On the computing paradigm and computational complexity, 82-92 [Zbl 1193.68116] \textit{Perrin, Dominique}, Symbolic dynamics and finite automata, 94-104 [Zbl 1193.68157] \textit{Vitányi, Paul}, Physics and the new computation, 106-128 [Zbl 1193.68110] \textit{Allender, Eric; Strauss, Martin}, Measure on P: Robustness of the notion, 129-138 [Zbl 1193.68111] \textit{Burtschick, Hans-Jörg}, Comparing counting classes for logspace, one-way logspace, and first-order, 139-148 [Zbl 1193.68113] \textit{Damm, Carsten; Holzer, Markus}, Automata that take advice, 149-158 [Zbl 1193.68152] \textit{Homer, Steven; Mocas, Sarah}, Nonuniform lower bounds for exponential time classes, 159-168 [Zbl 1188.68145] \textit{Kaufmann, Susanne; Kummer, Martin}, On a quantitative notion of uniformity, 169-178 [Zbl 1193.68117] \textit{Merkle, Wolfgang; Wang, Yongge}, Separations by random oracles and ``almost'' classes for generalized reducibilities, 179-190 [Zbl 1193.03071] \textit{Beauquier, Danièle; Burago, Dima; Slissenko, Anatol}, On the complexity of finite memory policies for Markov decision processes, 191-200 [Zbl 1193.68126] \textit{Hofmeister, Thomas; Lefmann, Hanno}, Derandomization for sparse approximations and independent sets, 201-210 [Zbl 1193.68133] \textit{Katajainen, Jyrki; Pasanen, Tomi; Titan, George}, Asymptotically efficient in-place merging, 211-220 [Zbl 1193.68282] \textit{Heusch, Peter}, The complexity of the falsifiability problem for pure implicational formulas, 221-226 [Zbl 1193.68132] \textit{Kann, Viggo}, Strong lower bounds on the approximability of some NPO PB-complete maximization problems, 227-236 [Zbl 1193.68120] \textit{Lefmann, Hanno; Savický, Petr}, Some typical properties of large AND/OR Boolean formulas, 237-246 [Zbl 1193.03018] \textit{Hühne, Martin}, The hedge: an efficient storage device for Turing machines with one head, 247-256 [Zbl 1193.68109] \textit{Maruyama, Osamu; Miyano, Satoru}, Graph inference from a walk for trees of bounded degree 3 is NP-complete, 257-266 [Zbl 1193.68197] \textit{Stojmenović, Ivan}, Honeycomb networks, 267-276 [Zbl 1193.68039] \textit{Fischer, Sophie; Hemaspaandra, Lane; Torenvliet, Leen}, Witness-isomorphic reductions and the local search problem (extended abstract), 277-287 [Zbl 1193.03070] \textit{Bertram-Kretzberg, Claudia; Hofmeister, Thomas}, Multiple product modulo arbitrary numbers, 288-298 [Zbl 1193.68127] \textit{Meinel, Christoph; Waack, Stephan}, Lower bounds for the majority communication complexity of various graph accessibility problems, 299-308 [Zbl 1193.68137] \textit{Bertoni, Alberto; Mereghetti, Carlo; Pighizzini, Giovanni}, Strong optimal lower bounds for Turing machines that accept nonregular languages, 309-318 [Zbl 1193.68119] \textit{Žák, Stanislav}, A superpolynomial lower bound for \((1,+k(n))\)-branching programs, 319-325 [Zbl 1193.68121] \textit{Breveglieri, Luca; Cherubini, Alessandra; Reghizzi, Stefano Crespi}, Deterministic parsing for augmented context-free grammars, 326-336 [Zbl 1193.68144] \textit{Mignosi, Filippo; Restivo, Antonio; Salemi, Sergio}, A periodicity theorem on words and applications, 337-348 [Zbl 1193.68202] \textit{Hotz, Günter; Pitsch, Gisela}, A new approach to analyse coupled-context-free languages, 349-358 [Zbl 1193.68153] \textit{Hermann, Miki; Kolaitis, Phokion G.}, Computational complexity of simultaneous elementary matching problems, 359-370 [Zbl 1193.03027] \textit{Krishna Rao, M. R. K.}, Graph reducibility of term rewriting systems, 371-381 [Zbl 1193.68147] \textit{Urzyczyn, Pawel}, Positive recursive type assignment, 382-391 [Zbl 1193.68076] \textit{Kranakis, Evangelos; Krizanc, Danny; Luccio, Flaminia L.}, String recognition on anonymous rings, 392-401 [Zbl 1193.68292] \textit{Róka, Zsuzsanna}, The firing squad synchronization problem on Cayley graphs, 402-411 [Zbl 1193.68170] \textit{Sibeyn, Jop F.; Kaufmann, Michael}, Solving cheap graph problems on meshes, 412-422 [Zbl 1193.68199] \textit{Burkart, Olaf; Caucal, Didier; Steffen, Bernhard}, An elementary bisimulation decision procedure for arbitrary context-free processes, 423-433 [Zbl 1193.68172] \textit{Bauget, Serge; Gastin, Paul}, On congruences and partial orders, 434-443 [Zbl 1193.68171] \textit{Corradini, Flavio; Gorrieri, Roberto; Roccetti, Marco}, Performance preorder: ordering processes with respect to speed, 444-453 [Zbl 1193.68173] \textit{Ferreira, W.; Hennessy, M.}, Towards a semantic theory of CML, 454-466 [Zbl 1193.68068] \textit{Huguet, Sébastien; Petit, Antoine}, Modular constructions of distributing automata, 467-478 [Zbl 1193.68154] \textit{Sangiorgi, Davide}, On the proof method for bisimulation, 479-488 [Zbl 1193.68177] \textit{Martin, Clare}, Towards a calculus of predicate transformers, 489-498 [Zbl 1193.68165] \textit{Abadi, Martín; Merz, Stephan}, An abstract account of composition, 499-508 [Zbl 1193.68159] \textit{van der Goot, Roel; de Bruin, Arie}, Syntax and semantics of Procol, 509-518 [Zbl 1193.68072] \textit{Godskesen, Jens Chr.; Larsen, Kim G.}, Synthesizing distinguishing formulae for real time systems -- extended abstract, 519-528 [Zbl 1193.68162] \textit{Laroussinie, François; Larsen, Kim G.; Weise, Carsten}, From timed automata to logic -- and back, 529-539 [Zbl 1193.03069] \textit{Makowsky, J. A.; Ravve, E. V.}, Incremental model checking for decomposable structures, 540-551 [Zbl 1193.68164] \textit{Janin, David; Walukiewicz, Igor}, Automata for the modal \(\mu \)-calculus and related results, 552-562 [Zbl 1193.68163] \textit{Niebert, Peter}, A \(\nu \)-calculus with local views for systems of sequential agents, 563-573 [Zbl 1193.68166] \textit{Feinsilver, P.; Schott, R.}, An operator calculus approach to the evolution of dynamic data structures, 574-586 [Zbl 1193.68084]