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

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.

---

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.

---

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.
Content:
Front Matter....Pages -
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
Stochastic automata and length distributions of rational languages....Pages 170-180
Towards a categorical semantics of type classes....Pages 181-190
Single-path Petri nets....Pages 191-201
The bisection problem for graphs of degree 4 (configuring transputer systems)....Pages 202-210
Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata....Pages 211-220
Infinite normal forms for non-linear term rewriting systems....Pages 221-230
Two algorithms for approxmate string matching in static texts....Pages 231-239
Efficient constructions of test sets for regular and context-free languages....Pages 240-248
The complexity of the reliable connectivity problem....Pages 249-258
Pattern matching in order-sorted languages....Pages 259-266
Two over three: a two-valued logic for software specification and validation over a three-valued predicate calculus....Pages 267-276
A solution of the complement problem in associatiue-commutatiue theories....Pages 277-286
A model for real-time systems....Pages 287-297
On strict codes....Pages 298-307
A decidable case of the semi-unification problem....Pages 308-317
Maintaining dictionaries in a hierarchical memory....Pages 318-327
Upper and lower bounds for certain GRAPH-ACCESSIBILITY-PROBLEMs on bounded alternating ?-BRANCHING PROGRAMs....Pages 328-336
CCS dynamic bisimulation is progressing....Pages 337-345
Syntax and semantics of a monotonic framework for non-monotonic reasoning....Pages 346-356
On the cardinality of sets of infinite trees recognizable by finite automata....Pages 357-366
Extending temporal logic by explicit concurrency....Pages 367-376
An extensional partial combinatory algebra based on ?-terms....Pages 377-386
Once more on order-sorted algebras....Pages 387-396
Composition of two semi commutations....Pages 397-405
An efficient decision algorithm for the uniform semi-unification problem extended abstract....Pages 406-414
Different modifications of pointer machines and their computational power....Pages 415-425
Back Matter....Pages 426-435
....Pages -