Mathematical Foundations of Computer Science 1990 Banska Bystrica, Czechoslovakia, August 27-31, 1990 Proceedings

This volume contains papers selected for presentation at the 15th Symposium on Mathematical Foundations of Computer Science, MFCS '90, held at Banská Bystrica, Czechoslovakia, August 27-31, 1990. Previous MFCS proceedings have also been published in the Lecture Notes in Computer Science. This symposium is the 15th in a series of international meetings which have taken place in Czechoslovakia and Poland. The aim of these symposia is to bring together specialists in theoretical fields of computer science from various countries and to stimulate mathematical research in theoretical computer science. These proceedings consist of 10 invited papers and 52 communications selected by the international Program Committee. The papers present the latest results in key areas of computer science by authors from Europe, USA, Japan and China.

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 ofhigher order processes.- The membership problem for context-free chain code picture languages.- Optimal algorithms for dissemination of information in some interconnection networks.- A hierarchy of compositional models of I/O-automata (Extended Abstract).- Minimal nontrivial space complexity of probabilistic one- way turing machines.- On the complexity of genuinely polynomial computation.- Pumping lemmrs for tree languages generated by rewrite systems.- Vector language: Simple description of hard instances.- Separating ?L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time.- The use of graphs of elliptical influence in visual hierarchical clustering.- Characterizing unambiguous augmented pushdown automata by circuits.- Rational ?-transductions.- Splitsort—an adaptive sorting algorithm.- Equational calculi for many-sorted algebras with empty carrier sets.- Semi-commutation and deterministic petri nets.- Internal labellings in lambda-calculus.- A sup-preserving completion of ordered partial algebras.- ATIME(n) is closed under Counting.- Investigation of finitary calculi for the temporal logics by means of infinitary calculi.- Typed horn logic (extended abstract).- Results on the glory of the past.- A stronger version of parikh theorem.- The parallel complexity of some constructions in combinatorial group theory (abstract).- Gentzen type axiomatization for PAL.- Distance automata having large finite distance or finite ambiguity.- Bottom-up-heap sort, a new variant of heap sort beating on average quick sort (if n is not very small).- Symmetric functions in AC 0 can be computed in constant depth with very small size.- The k-section of treewidth restricted graphs.- Computing large polynomial powers very fast in parallel.