Mathematical Foundations of Computer Science 1991: 16th International Symposium, Kazimierz Dolny, Poland, September 9-13, 1991. Proceedings (Lecture Notes in Computer Science, 520)

This volume contains the proceedings of the 16th International Symposium on Mathematical Foundations of Computer Science, MFCS '91, held in Kazimierz Dolny, Poland, September 9-13, 1991. The series of MFCS symposia, organized alternately in Poland and Czechoslovakia since 1972, has a long and well established tradition. The purpose of the series is to encourage high-quality research in all branches of theoretical computer science and to bring together specialists working actively in the area. Principal areas of interest in this symposium include: software specification and development, parallel and distributed computing, logic and semantics of programs, algorithms, automata and formal languages, complexity and computability theory, and others. The volume contains 5 invited papers by distinguished scientists and 38 contributions selected from a total of 109 submitted papers. Elimination of negation in term algebras....Pages 1-16 Rewrite orderings and termination of rewrite systems....Pages 17-27 On the faithfulness of formal models....Pages 28-42 Models for concurrency....Pages 43-46 On a hierarchy of file types and a tower of their theories....Pages 47-63 Strong conjunction and intersection types....Pages 64-73 Partial higher-order specifications....Pages 74-83 Unification in incompletely specified theories: A case study....Pages 84-92 Observing localities....Pages 93-102 Abstract dynamic data types: A temporal logic approach....Pages 103-112 Generating words by cellular automata....Pages 113-120 Atomic refinement in process description languages....Pages 121-130 Recognizable complex trace languages (abstract)....Pages 131-140 Solving systems of linear diophantine equations: An algebraic approach....Pages 141-150 A second-order pattern matching algorithm for the cube of typed λ-calculi....Pages 151-160 The lazy call-by-value λ-calculus....Pages 161-169 The limit of split n -bisimulations for CCS agents....Pages 170-180 Stochastic automata and length distributions of rational languages....Pages 181-190 Towards a categorical semantics of type classes....Pages 191-201 Single-path Petri nets....Pages 202-210 The bisection problem for graphs of degree 4 (configuring transputer systems)....Pages 211-220 Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata....Pages 221-230 Infinite normal forms for non-linear term rewriting systems....Pages 231-239 Two algorithms for approxmate string matching in static texts....Pages 240-248 Efficient constructions of test sets for regular and context-free languages....Pages 249-258 The complexity of the reliable connectivity problem....Pages 259-266 Pattern matching in order-sorted languages....Pages 267-276 Two over three: a two-valued logic for software specification and validation over a three-valued predicate calculus....Pages 277-286 A solution of the complement problem in associatiue-commutatiue theories....Pages 287-297 A model for real-time systems....Pages 298-307 On strict codes....Pages 308-317 A decidable case of the semi-unification problem....Pages 318-327 Maintaining dictionaries in a hierarchical memory....Pages 328-336 Upper and lower bounds for certain GRAPH-ACCESSIBILITY-PROBLEMs on bounded alternating ω-BRANCHING PROGRAMs....Pages 337-345 CCS dynamic bisimulation is progressing....Pages 346-356 Syntax and semantics of a monotonic framework for non-monotonic reasoning....Pages 357-366 On the cardinality of sets of infinite trees recognizable by finite automata....Pages 367-376 Extending temporal logic by explicit concurrency....Pages 377-386 An extensional partial combinatory algebra based on λ-terms....Pages 387-396 Once more on order-sorted algebras....Pages 397-405 Composition of two semi commutations....Pages 406-414 An efficient decision algorithm for the uniform semi-unification problem extended abstract....Pages 415-425 Different modifications of pointer machines and their computational power....Pages 426-435 Plotkin [36] proposed a formal model for inductive inference which was based upon Pop-plestone's suggestion that Since unification is useful in automatic deduction, its dual might prove helpful for induction. 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. This volume contains papers selected for presentation at the 15th Symposium on Mathematical Foundations of Computer Science, MFCS '90, held at Banska Bystrica, Czechoslovakia, August 27-31, 1990.