Mathematical Foundations of Computer Science 1990

A logical operational semantics of full Prolog.- Syntactic theories.- On kleene algebras and closed semirings.- Interactive computations of optimal solutions.- Restricted branching programs and their computational power.- Dynamic hashing strategies.- One-way functions in complexity theory.- Type inference problems: A survey.- Counting the number of solutions.- Implementation of parallel graph reduction by explicit annotation and program transformation.- Interrogative complexity of ?-languages' recognition.- On the power of uniform families of constant depth threshold circuits.- Separating sets of hyperrectangles.- On preemptive scheduling of periodic, real-time tasks on one processor.- Retractions in comparing prolog semantics (extended abstract).- Using inductive counting to simulate nondeterministic computation.- Some properties of zerotesting bounded one-way multicounter machines.- On fast algorithms for two servers.- Decomposition of semi commutations.- Parallel construction of minimal suffix and factor automata.- Affine automata: A technique to generate complex images.- The complexity of symmetric functions in parity normal forms.- Event structures, causal trees, and refinements.- Query languages which express all PTIME queries for trees and unicyclic graphs.- Comparisons among classes of Y-tree systolic automata.- On checking versus evaluation of multiple queries.- Generalized kolmogorov complexity in relativized separations.- A first-order logic for partial recursive functions.- Speed-up theorem without tape compression.- On possibilities of one-way synchronized and alternating automata.- Unrestricted resolution versus N-resolution.- Quality criteria for partial order semantics of place/transition-nets.- Tree-stack automata.- Specification & verification of higher order processes.- The membership problem for context-free chain code picture languages.- Optimal algorithms for dissemination of information in some interconnection networks.- A hierarchyof