Mathematical foundations of computer science 1998. 23rd international symposium, MFCS '98. Brno, Czech Republic, August 24--28, 1998. Proceedings (Q1264333)

The articles of mathematical interest will be reviewed individually. The 21st symposium (1996) has been announced (see Zbl 0852.00041). Indexed articles: \textit{Ausiello, Giorgio; Italiano, Giuseppe F.; Nanni, Umberto}, Hypergraph traversal revisited: Cost measures and dynamic algorithms, 1-16 [Zbl 0916.05054] \textit{Harel, David}, Towards a theory of recursive structures, 36-53 [Zbl 0972.03037] \textit{Nielsen, Mogens}, Reasoning about the past, 117-128 [Zbl 0917.68075] \textit{Pudlák, Pavel}, Satisfiability -- algorithms and logic (extended abstract), 129-141 [Zbl 0911.03018] \textit{Stirling, Colin}, The joys of bisimulation, 142-151 [Zbl 0942.68075] \textit{Aldaz, Mikel; Heintz, Joos; Matera, Guillermo; Montaña, José L.; Pardo, Luis M.}, Combinatorial hardness proofs for polynomial evaluation (extended abstract), 167-175 [Zbl 0911.68084] \textit{Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann}, Minimum propositional proof length is NP-hard to linearly approximate (extended abstract), 176-184 [Zbl 0911.03028] \textit{Kuzjurin, Nikolai N.}, Locally explicit construction of Rődl's asymptotically good packings, 194-202 [Zbl 0911.05027] \textit{Baaz, Matthias; Ciabattoni, Agata; Fermüller, Christian; Veith, Helmut}, Proof theory of fuzzy logics: Urquhart's \(C\) and related logics, 203-212 [Zbl 0921.03028] \textit{Bonner, Richard; Freivalds, Rūsiņš; Lapiņš, Jānis; Lukjanska, Antra}, Nonstochastic languages as projections of 2-tape quasideterministic languages, 213-219 [Zbl 0917.68120] \textit{Rabinovich, Alexander}, Expressive completeness of temporal logic of action, 229-238 [Zbl 0912.03011] \textit{Touzet, Hélène}, Encoding the hydra battle as a rewrite system, 267-276 [Zbl 1113.68419] \textit{Hagenah, Christian; Muscholl, Anca}, Computing \(\varepsilon\)-free NFA from regular expressions in \(O(n\log^2(n))\) time, 277-285 [Zbl 0912.68113] \textit{Petersen, Holger}, The head hierarchy for oblivious finite automata with polynomial advice collapses, 296-304 [Zbl 0911.68147] \textit{Sénizergues, Géraud}, The equivalence problem for deterministic pushdown transducers into abelian groups, 305-315 [Zbl 0912.68139] \textit{Barthe, Gilles}, The semi-full closure of pure type systems, 316-325 [Zbl 0912.03010] \textit{Benke, Marcin}, Predicative polymorphic subtyping, 326-335 [Zbl 0914.03035] \textit{Bierman, G. M.}, A computational interpretation of the \(\lambda\mu\)-calculus, 336-345 [Zbl 0912.03009] \textit{Chrząszcz, Jacek}, Polymorphic subtyping without distributivity, 346-355 [Zbl 0914.03017] \textit{Gastin, Paul; Meyer, Raphaël; Petit, Antoine}, A (non-elementary) modular decision procedure for LTrL, 356-365 [Zbl 0914.03010] \textit{Srba, Jiří}, Deadlocking states in context-free process algebra, 388-398 [Zbl 0917.68153] \textit{Amano, Kazuyuki; Maruoka, Akira}, A superpolynomial lower bound for a circuit computing the clique function with at most \((1/6)\log \log n\) negation gates, 399-408 [Zbl 0914.94027] \textit{Ambainis, Andris; Barrington, David Mix; Huong LêThanh}, On counting \(AC^0\) circuits with negative constants, 409-417 [Zbl 0912.68055] \textit{Hemaspaandra, Lane A.; Rothe, Jörg}, A second step towards circuit complexity-theoretic analogs of Rice's theorem, 418-426 [Zbl 0914.03051] \textit{Emerson, E. Allen; Trefler, Richard J.}, Model checking real-time properties of symmetric systems, 427-436 [Zbl 0913.03036] \textit{Grohe, Martin; Schwentick, Thomas}, Locality of order-invariant first-order formulas, 437-445 [Zbl 0912.03017] \textit{Simpson, Alex K.}, Lazy functional algorithms for exact real functionals, 456-464 [Zbl 0913.65009] \textit{Ambos-Spies, Klaus; Lempp, Steffen; Mainhardt, Gunther}, Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets, 465-473 [Zbl 0912.03023] \textit{Bentzien, Levke}, Positive Turing and truth-table completeness for NEXP are incomparable, 474-482 [Zbl 0916.03030] \textit{Goldsmith, Judy; Ogihara, Mitsunori; Rothe, Jörg}, Tally NP sets and easy census functions, 483-492 [Zbl 0914.68078] \textit{Köbler, Johannes; Schuler, Rainer}, Average-case intractability vs. worst-case intractability, 493-502 [Zbl 0914.68079] \textit{Harju, Tero; Mateescu, Alexandru; Salomaa, Arto}, Shuffle on trajectories: The Schützenberger product and related operations, 503-511 [Zbl 0914.68112] \textit{Kuich, Werner}, Gaußian elimination and a characterization of algebraic power series, 512-521 [Zbl 0918.68059] \textit{Lopez, Luis-Miguel; Narbel, Philippe}, D0L-systems and surface automorphisms, 522-532 [Zbl 0914.68113] \textit{Ryl, Isabelle; Roos, Yves; Clerbout, Mireille}, About synchronization languages, 533-542 [Zbl 0914.68114] \textit{Barthelmann, Klaus}, When can an equational simple graph be generated by hyperedge replacement?, 543-552 [Zbl 0917.05054] \textit{Große-Rhode, Martin; Parisi-Presicce, Francesco; Simeoni, Marta}, Spatial and temporal refinement of typed graph transformation systems, 553-561 [Zbl 0910.18001] \textit{Hofmeister, Thomas; Lefmann, Hanno}, Approximating maximum independent sets in uniform hypergraphs, 562-570 [Zbl 0917.05055] \textit{La Torre, Salvatore; Napoli, Margherita}, Representing hyper-graphs by regular languages, 571-579 [Zbl 0915.05092] \textit{Iwama, Kazuo; Iwamoto, Chuzo}, Improved time and space hierarchies of one-tape off-line TMs, 580-588 [Zbl 0920.03049] \textit{Mielniczuk, Pawel; Pacholski, Leszek}, Tarskian set constraints are in NEXPTIME, 589-596 [Zbl 0914.03050] \textit{Vorobyov, Sergei}, \(\forall\exists^*\)-equational theory of context unification is \(\Pi_1^0\)-hard, 597-606 [Zbl 0912.03006] \textit{Wiedermann, Jiří}, Speeding-up nondeterministic single-tape off-line computations by one alternation (extended abstract), 607-615 [Zbl 0912.03022] \textit{Courcelle, Bruno; Lapoire, Denis}, Facial circuits of planar graphs and context-free languages, 616-624 [Zbl 0914.68115] \textit{Iwama, Kazuo; Nozoe, Mitsushi; Yajima, Shuzo}, Optimizing OBDDs is still intractable for monotone functions, 625-635 [Zbl 1031.68539] \textit{Preuß, Harry; Srivastav, Anand}, Blockwise variable orderings for shared BDDs (extended abstract), 636-644 [Zbl 1031.68540] \textit{Slobodová, Anna}, On the composition problem for OBDDs with multiple variable orders, 645-655 [Zbl 0919.94053] \textit{Choffrut, Christian; Horvath, Sandor}, Equations in transfinite strings, 656-664 [Zbl 0914.68152] \textit{Crochemore, M.; Mignosi, F.; Restivo, A.}, Minimal forbidden words and factor automata, 665-673 [Zbl 0914.68153] \textit{Karhumäki, Juhani; Maňuch, Ján; Plandowski, Wojciech}, On defect effect of bi-infinite words, 674-682 [Zbl 0914.68154] \textit{Kolpakov, Roman; Kucherov, Gregory; Tarannikov, Yuri}, On repetition-free binary words of minimal density (extended abstract), 683-692 [Zbl 0912.68159] \textit{Bodlaender, Hans L.; Hagerup, Torben}, Tree decompositions of small diameter, 702-712 [Zbl 0918.05043] \textit{Broersma, Hajo; Huck, Andreas; Kloks, Ton; Koppius, Otto; Kratsch, Dieter; Müller, Haiko; Tuinstra, Hilde}, Degree-preserving forests, 713-721 [Zbl 0916.05019] \textit{Crauser, A.; Mehlhorn, K.; Meyer, U.; Sanders, P.}, A parallelization of Dijkstra's shortest path algorithm, 722-731 [Zbl 0912.05056] \textit{Durand, Bruno; Porrot, Sylvain}, Comparison between the complexity of a function and the complexity of its graph, 732-739 [Zbl 0914.68109] \textit{Fernau, Henning; Staiger, Ludwig}, IFS and control languages, 740-750 [Zbl 0918.68060] \textit{Matz, Oliver}, One quantifier will do in existential monadic second-order logic over pictures, 751-759 [Zbl 0912.03004] \textit{Weihrauch, Klaus; Zheng, Xizhong}, A finite hierarchy of the recursively enumerable real numbers, 798-806 [Zbl 0920.03054] \textit{Buchholz, Thomas; Klein, Andreas; Kutrib, Martin}, One guess one-way cellular arrays, 807-815 [Zbl 0914.68142] \textit{Cattaneo, Gianpiero; Margara, Luciano}, Topological definitions of chaos applied to cellular automata dynamics, 816-824 [Zbl 1022.37012] \textit{Manzini, Giovanni}, Characterization of sensitive linear cellular automata with respect to the counting distance, 825-833 [Zbl 0918.68068] \textit{Mazoyer, Jacques; Rapaport, Ivan}, Additive cellular automata over \(\mathbb{Z}_p\) and the bottom of \((CA,\leq)\), 834-843 [Zbl 0914.68143]