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

J-L. Lassez, M. Maher, K. Marriott (auth.), Andrzej Tarlecki (eds.)3540543457, 9783540543459

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.

---

Table of contents :
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