Mathematical Foundations of Computer Science 1988

Sparse sets, tally sets, and polynomial reducibilities.- Functional programming and combinatory algebras.- On models and algebras for concurrent processes.- String matching with constraints.- Structure of complexity classes: Separations, collapses, and completeness.- Inductive syntactical synthesis of programs from sample computations.- 3-dimensional shortest paths in the presence of polyhedral obstacles.- Robust oracle machines.- Recognizable sets with multiplicities in the tropical semiring.- Reusable specification components.- Comparing interconnection networks.- Probabilistic automata complexity of languages depends on language structure and error probability.- Breadth-first phrase structure grammars and queue automata.- Implementing abstract data structures in hardware.- Distribution of Sequential Processes.- Automata and rational expressions on planar graphs.- On maximal prefix sets of words.- Infinite behaviour of deterministic petri nets.- Testing isomorphism of outerplanar graphs in parallel.- Efficient simulations between concurrent-read concurrent-write pram models.- Multiple propositional dynamic logic of parallel programs.- The steiner tree problem and homogeneous sets.- Termination of rewriting is undecidable in the one-rvle case.- Local checking of trace synchronizability.- Edge separators for planar graphs and their applications.- A fast parallel algorithm for eigenvalue problem of jacobi matrices.- Strong and robustly strong polynomial time reducibilities to sparse sets.- Context-free-like forms for the phrase-structure grammars.- On the expressive strength of the finitely typed lambda - terms.- Hoare calculi for higher - type control siructures and their completeness in the sense of cook.- On representing CCS programs by finite petri nets.- Ataxonomy of fairness and temporal logic problems for petri nets.- Branching programs as a tool for proving lower bounds on vlsi computations and optimal algorithms for systolic arrays.- Two lower bounds for circuits over the basis (&, V, -).- Positive/Negative conditional rewriting.- On the computational complexity of codes in graphs.- Separating the eraser turing machine classes Le, NLe, co-NLe and Pe.- Compositional proofs by partial specification of processes.- Introducing negative information in relational databases.- On positive occur-checks in unification.- Two applications of fürer's counter to one-tape nondeterministic TMs.- ? 2 p -complete lexicographically first maximal subgraph problems.- Proof system for weakest prespecification and its applications.- On complexity of counting.- Design, proof and analysis of new efficient algorithms for incremental attribute evaluation.- On efficiency of interval routing algorithms.- An almost linear robinson unification algorithm.- Random boolean formulas representing any boolean function with asymptotically equal probability.- On the power of communication in alternating machines.- Classes of cnf-formulas with backtracking trees of exponential or linear average order for exact-satisfiability.- Bisections of free monoids and a new unavoidable regularity.- Failures semantics and deadlocking of modular petri nets.- A decomposition theorem for finite-valued transducers and an application to the equivalence problem.