Mathematical Foundations of Computer Science 1991: 16th International Symposium, Kazimierz Dolny, Poland, September 9-13, 1991. Proceedings

ISBN-13: 9783540543459 / Angielski / Miękka / 1991 / 437 str.

Andrzej Tarlecki

Opis

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.

Spis treści

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.