Mathematical foundations of computer science 1992. 17th international symposium, Prague, Czechoslovakia, August 24–28, 1992. Proceedings. (English) Zbl 1415.68030

Lecture Notes in Computer Science 629. Berlin: Springer (ISBN 978-3-540-55808-8/pbk; 978-3-540-47291-9/ebook). ix, 521 p. (1992).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 0753.00030].
Indexed articles:
Agarwal, Pankaj K.; Matoušek, Jiří, On range searching with semialgebraic sets, 1-13 [Zbl 1493.68366]
Díaz, J., Graph layout problems, 14-23 [Zbl 1493.68265]
Lange, Klaus-Jörn; Rossmanith, Peter; Rytter, Wojciech, Parallel recognition and ranking of context-free languages, 24-36 [Zbl 1493.68192]
Mihail, Milena, On the expansion of combinatorial polytopes, 37-49 [Zbl 1493.68276]
Orponen, Pekka, Neural networks and complexity theory, 50-61 [Zbl 1493.68140]
Tucker, J. V.; Zucker, J. I., Theory of computation over stream algebras, and its applications, 62-80 [Zbl 1493.68142]
Watanabe, Osamu, On the complexity of small description and related topics, 82-94 [Zbl 1493.68154]
Wiedermann, Juraj, Weak parallel machines: a new class of physically feasible parallel machine models, 95-111 [Zbl 1493.68143]
Wigderson, Avi, The complexity of graph connectivity, 112-132 [Zbl 1493.68163]
Bast, Holger; Dietzfelbinger, Martin; Hagerup, Torben, A perfect parallel dictionary, 133-141 [Zbl 1493.68134]
Becker, Bernd; Hartmann, Joachim, Some remarks on the test complexity of iterative logic arrays (extended abstract), 142-152 [Zbl 1493.94068]
Burtschick, Hans-Jörg; Hoene, Albrecht, The degree structure of 1-L reductions, 153-161 [Zbl 1496.03165]
Cai, Jin-Yi; Hemachandra, Lane A.; Vyskoč, Jozef, Promise problems and access to unambiguous computation, 162-171 [Zbl 1493.68157]
Chari, Suresh; Ranjan, Desh; Rohatgi, Pankaj, On the complexity of incremental computation (extended abstract), 172-180 [Zbl 1493.68158]
Choffrut, Christian; Goldwurm, Massimiliano, Rational transductions and complexity of counting problems, 181-190 [Zbl 1493.68185]
Comon, Hubert; Fernández, Maribel, Negation elimination in equational formulae (extended abstract), 191-199 [Zbl 1496.03040]
Costa, J. F.; Sernadas, A.; Sernadas, C.; Ehrich, H.-D., Object interaction, 200-208 [Zbl 1493.68242]
Curien, P.-L.; Hardin, T.; Ríos, A., Strong normalization of substitutions, 209-217 [Zbl 1496.03059]
Daley, Robert; Kalyanasundaram, Bala, Probabilistic and pluralistic learners with mind changes (extended abstract), 218-226 [Zbl 1493.68166]
Damm, Carsten; Holzer, Markus; Lange, Klaus-Jörn, Parallel complexity of iterated morphisms and the arithmetic of small numbers, 227-235 [Zbl 1493.68186]
Derencourt, D.; Karhumäki, J.; Latteux, M.; Terlutte, A., On computational power of weighted finite automata, 236-245 [Zbl 1493.68187]
Feldmann, Rainer; Mysliwietz, Peter, The shuffle exchange network has a Hamiltonian path, 246-254 [Zbl 1494.68193]
Gastin, Paul; Petit, Antoine, Poset properties of complex traces, 255-263 [Zbl 1493.68197]
Goerdt, Andreas, A threshold for unsatisfiability, 264-274 [Zbl 1494.68095]
Gold, Robert, Dataflow semantics for Petri nets, 275-283 [Zbl 1493.68246]
Guessarian, Irène; Veloso-Peixoto, Marcos, About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs, 284-297 [Zbl 1493.68069]
Hagerup, Torben; Petersson, Ola, Merging and sorting strings in parallel, 298-306 [Zbl 1493.68409]
Jančar, Petr; Mráz, František; Plátek, Martin, Characterization of context-free languages by erasing automata, 307-314 [Zbl 1494.68140]
Kari, Lila, Insertion and deletion of words: determinism and reversibility, 315-326 [Zbl 1493.68283]
Kascak, Frantisek, Small universal one-state linear operator algorithm, 327-335 [Zbl 1493.68392]
Laneve, Cosimo; Montanari, Ugo, Mobility in the cc-paradigm, 336-345 [Zbl 1493.68249]
Lange, Klaus-Jörn; Rossmanith, Peter, The emptiness problem for intersections of regular languages, 346-354 [Zbl 1493.68191]
Leung, Hing, On finite automata with limited nondeterminism (extended abstract), 355-363 [Zbl 1493.68194]
Litovsky, Igor; Métivier, Yves; Sopena, Eric, Definitions and comparisons of local computations on graphs (extended abstract), 364-373 [Zbl 1493.68176]
Martin, Bruno, Efficient unidimensional universal cellular automaton, 374-382 [Zbl 1493.68235]
Maruyama, Osamu; Miyano, Satoru, Inferring a tree from walks, 383-391 [Zbl 1493.68275]
Mayordomo, Elvira, Almost every set in exponential time is P-bi-immune, 392-400 [Zbl 1493.68152]
Murphy, David; Poigné, Axel, A functorial semantics for observed concurrency, 401-411 [Zbl 1493.68251]
Ochmański, Edward, Modelling concurrency with semi-commutations, 412-420 [Zbl 1493.68252]
Pedersen, John, Decision problems for cellular automata and their semigroups, 421-429 [Zbl 1493.68236]
Pinna, G. Michele; Poigné, Axel, On the nature of events, 430-441 [Zbl 1493.68253]
Preilowski, W.; Dahlhaus, E.; Wechsung, G., New parallel algorithms for convex hull and triangulation in 3-dimensional space, 442-450 [Zbl 1493.68374]
Przymusinski, Teodor C., Two simple characterizations of well-founded semantics, 451-462 [Zbl 1493.68074]
Ramesh, S., Fully abstract semantics for higher order communicating systems (extended abstract), 463-471 [Zbl 1493.68256]
Reimen, Nicolas, Superposable trellis automata, 472-482 [Zbl 1493.68237]
Roos, Thomas; Albers, Gerhard, Maintaining proximity in higher dimensional spaces (extended abstract), 483-493 [Zbl 1494.68274]
Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey, Characterizing regular languages with polynomial densities, 494-503 [Zbl 1493.68195]
Wang, Dongming, A strategy for speeding-up the computation of characteristic sets, 504-510 [Zbl 1493.68405]
Wrathall, C.; Diekert, V.; Otto, F., One-rule trace-rewriting systems and confluence, 511-521 [Zbl 1493.68180]


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


Zbl 0753.00030
Full Text: DOI