Mathematical Foundations of Computer Science 1992

On range searching with semialgebraic sets.- Graph layout problems.- Parallel recognition and ranking of context-free languages.- On the expansion of combinatorial polytopes.- Neural networks and complexity theory.- Theory of computation over stream algebras, and its applications.- Methods in parallel algorithmcs.- On the complexity of small description and related topics.- Weak parallel machines: A new class of physically feasible parallel machine models.- The complexity of graph connectivity.- A perfect parallel dictionary.- Some remarks on the test complexity of iterative logic arrays.- The degree structure of 1-L reductions.- Promise problems and access to unambiguous computation.- On the complexity of incremental computation.- Rational transductions and complexity of counting problems.- Negation elimination in equational formulae.- Object interaction.- Strong normalization of substitutions.- Probabilistic and pluralistic learners with mind changes.- Parallel complexity of iterated morphisms and the arithmetic of small numbers.- On computational power of weighted finite automata.- The shuffle exchange network has a Hamiltonian path.- Poset properties of complex traces.- A threshold for unsatisfiability.- Dataflow semantics for Petri nets.- About boundedness for some datalog and DATALOGneg programs.- Merging and sorting strings in parallel.- Characterization of context-pree languages by erasing automata.- Insertion and deletion of words: Determinism and reversibility.- Small universal one-state linear operator algorithm.- Mobility in the CC-paradigm.- The emptiness problem for intersections of regular languages.- On finite automata with limited nondeterminism (extended abstract).- Definitions and comparisons of local computations on graphs.- Efficient unidimensional universal cellular automaton.- Inferring a tree from walks.- Almost every set in exponential time is P-bi-immune.- A functorial semantics for observed concurrency.- Modelling concurrency with