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

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