Mathematical Foundations of Computer Science 1991

This volume contains the proceedings of a Polish/Czechoslovakian symposium on topics including parallel and distributed computing, software specification and development, logic and semantics of programs, algorithms, complexity and computability theory.

Inhalt
Elimination of negation in term algebras.- Rewrite orderings and termination of rewrite systems.- On the faithfulness of formal models.- Models for concurrency.- On a hierarchy of file types and a tower of their theories.- Strong conjunction and intersection types.- Partial higher-order specifications.- Unification in incompletely specified theories: A case study.- Observing localities.- Abstract dynamic data types: A temporal logic approach.- Generating words by cellular automata.- Atomic refinement in process description languages.- Recognizable complex trace languages (abstract).- Solving systems of linear diophantine equations: An algebraic approach.- A second-order pattern matching algorithm for the cube of typed ?-calculi.- The lazy call-by-value ?-calculus.- The limit of split n -bisimulations for CCS agents.- Stochastic automata and length distributions of rational languages.- Towards a categorical semantics of type classes.- Single-path Petri nets.- The bisection problem for graphs of degree 4 (configuring transputer systems).- Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata.- Infinite normal forms for non-linear term rewriting systems.- Two algorithms for approxmate string matching in static texts.- Efficient constructions of test sets for regular and context-free languages.- The complexity of the reliable connectivity problem.- Pattern matching in order-sorted languages.- Two over three: a two-valued logic for software specification and validation over a three-valued predicate calculus.- A solution of the complement problem in associatiue-commutatiue theories.- A model for real-time systems.- On strict codes.- A decidable case of the semi-unification problem.- Maintaining dictionaries in a hierarchical memory.-Upper and lower bounds for certain GRAPH-ACCESSIBILITY-PROBLEMs on bounded alternating ?-BRANCHING PROGRAMs.- CCS dynamic bisimulation is progressing.- Syntax and semantics of a monotonic framework for non-monotonic reasoning.- On the cardinality of sets of infinite trees recognizable by finite automata.- Extending temporal logic by explicit concurrency.- An extensional partial combinatory algebra based on ?-terms.- Once more on order-sorted algebras.- Composition of two semi commutations.- An efficient decision algorithm for the uniform semi-unification problem extended abstract.- Different modifications of pointer machines and their computational power.