Mathematical Foundations of Computer Science 1992: 17th International Symposium Prague, Czechoslovakia, August 24–28, 1992 Proceedings

Pankaj K. Agarwal, Jiří Matoušek (auth.), Ivan M. Havel, Václav Koubek (eds.)354055808X, 9783540558088

This volume contains 10 invited papers and 40 short communications contributed for presentation at the 17th Symposium on Mathematical Foundations of Computer Science, held in Prague, Czechoslovakia, August 24-28, 1992. The series of MFCS symposia, organized alternately in Poland and Czechoslovakia since 1972, has a long and well established tradition. The purpose of the series is to encourage high-quality research in all branches of theoretical computer science and to bring together specialists working actively in the area. Numerous topics are covered in this volume. The invited papers cover: range searching with semialgebraic sets, graph layout problems, parallel recognition and ranking of context-free languages, expansion of combinatorial polytopes, neural networks and complexity theory, theory of computation over stream algebras, methods in parallel algorithms, the complexity of small descriptions, weak parallel machines, and the complexity of graph connectivity.

---

Table of contents :
On range searching with semialgebraic sets….Pages 1-13
Graph layout problems….Pages 14-23
Parallel recognition and ranking of context-free languages….Pages 24-36
On the expansion of combinatorial polytopes….Pages 37-49
Neural networks and complexity theory….Pages 50-61
Theory of computation over stream algebras, and its applications….Pages 62-80
Methods in parallel algorithmcs….Pages 81-81
On the complexity of small description and related topics….Pages 82-94
Weak parallel machines: A new class of physically feasible parallel machine models….Pages 95-111
The complexity of graph connectivity….Pages 112-132
A perfect parallel dictionary….Pages 133-141
Some remarks on the test complexity of iterative logic arrays….Pages 142-152
The degree structure of 1-L reductions….Pages 153-161
Promise problems and access to unambiguous computation….Pages 162-171
On the complexity of incremental computation….Pages 172-180
Rational transductions and complexity of counting problems….Pages 181-190
Negation elimination in equational formulae….Pages 191-199
Object interaction….Pages 200-208
Strong normalization of substitutions….Pages 209-217
Probabilistic and pluralistic learners with mind changes….Pages 218-226
Parallel complexity of iterated morphisms and the arithmetic of small numbers….Pages 227-235
On computational power of weighted finite automata….Pages 236-245
The shuffle exchange network has a Hamiltonian path….Pages 246-254
Poset properties of complex traces….Pages 255-263
A threshold for unsatisfiability….Pages 264-274
Dataflow semantics for Petri nets….Pages 275-283
About boundedness for some datalog and DATALOG neg programs….Pages 284-297
Merging and sorting strings in parallel….Pages 298-306
Characterization of context-pree languages by erasing automata….Pages 307-314
Insertion and deletion of words: Determinism and reversibility….Pages 315-326
Small universal one-state linear operator algorithm….Pages 327-335
Mobility in the CC-paradigm….Pages 336-345
The emptiness problem for intersections of regular languages….Pages 346-354
On finite automata with limited nondeterminism (extended abstract)….Pages 355-363
Definitions and comparisons of local computations on graphs….Pages 364-373
Efficient unidimensional universal cellular automaton….Pages 374-382
Inferring a tree from walks….Pages 383-391
Almost every set in exponential time is P-bi-immune….Pages 392-400
A functorial semantics for observed concurrency….Pages 401-411
Modelling concurrency with semi-commutations….Pages 412-420
Decision problems for cellular automata and their semigroups….Pages 421-429
On the nature of events….Pages 430-441
New parallel algorithms for convex hull and triangulation in 3-dimensional space….Pages 442-450
Two simple characterizations of well-founded semantics….Pages 451-462
Fully abstract semantics for higher order communicating systems….Pages 463-471
Superposable Trellis Automata….Pages 472-482
Maintaining proximity in higher dimensional spaces….Pages 483-493
Characterizing regular languages with polynomial densities….Pages 494-503
A strategy for speeding-up the computation of characteristic sets….Pages 504-510
One-rule trace-rewriting systems and confluence….Pages 511-521