Mathematical Foundations of Computer Science 1989

From specification languages to specification knowledge bases: The PTO approach.- Monadic second-order logic and context-free graph-grammars.- A thesis for bounded concurrency.- Space bounded computations : Review and new separation results.- Concurrent nondeterministic processes: Adequacy of structure and behaviour.- LEDA a library of efficient data types and algorithms.- Correctness of concurrent processes.- Understanding nets.- On the strength of temporal proofs.- Proof-theoretic characterisations of logic programming.- Algebraically closed theories.- Control flow versus logic: A denotational and a declarative model for Guarded Horn Clauses.- Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A constructive glimpse.- Parallel complexity of lexicographically first problems for tree-structured graphs.- On the power of synchronization in parallel computations.- Optimal parallel algorithms for the recognition and colouring outerplanar graphs.- Logical characterizations of nonmonotonic TMSs.- Proving correctness of constructor implementations.- Equivalence notions for concurrent systems and refinement of actions.- System simulation and the sensitivity of self-stabilization.- Polynomial-time functions generate SAT: On P-splinters.- Generalized definite tree languages.- Pinwheel scheduling with two distinct numbers.- Testing approximate symmetry in the plane is NP-hard.- Memory and algebra.- Integer relations among algebraic numbers.- An iterative metric fully abstract semantics for nondeterministic dataflow (extended abstract).- Complexity of decision problems under incomplete information.- On the nature of TELLUS.- Switching graphs and their complexity.- Pomset semantics for true concurrency with synchronization and recursion.- Oracle branching programs and Logspace versus P.- Generalizing singly-linked list reorganizing heuristics for doubly-linked lists.- Area complexity of merging.- Logically defined subsets of IN k .- An extended Herbrand theorem for first-order theories with equality interpreted in partial algebras.- Characterization of recognizable trace languages by distributed automata.- Knuth-Morris-Pratt algorithm: An analysis.- Pushdown automata on infinite trees and omega-Kleene closure of context-free tree sets.- An imperative type hierarchy with partial products.- A coloring algorithm for interval graphs.- Finite constants: Characterizations of a new decidable set of constants.- Optimal data flow analysis via observational equivalence.- One more method for proving lower bounds on the formula complexity of boolean functions.- The Hoare-like verification system for a language with an exception handling mechanism.- On the lengths of values in a finite transducer.- On varieties of languages closed under products with counter.- On the computational efficiency of symmetric neural networks.- Constructive aspects of the omega-rule : Application to proof systems in computer science and algorithmic logic.- How to define functionals on free structures in typed ? calculus.- Concurrency, modularity, and synchronization.- On comparing probabilistic and deterministic automata complexity of languages.