zbMATH — the first resource for mathematics

Mathematical foundations of computer science 1998. 23rd international symposium, MFCS ’98. Brno, Czech Republic, August 24–28, 1998. Proceedings. (English) Zbl 0895.00049
Lecture Notes in Computer Science. 1450. Berlin: Springer. xvii, 846 p. (1998).

Show indexed articles as search result.

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

00B25 Proceedings of conferences of miscellaneous specific interest
68-06 Proceedings, conferences, collections, etc. pertaining to computer science