CAAP ’90: 15th Colloquium on Trees in Algebra and Programming Copenhagen, Denmark, May 15–18, 1990 Proceedings

Tirza Hirst, David Harel (auth.), A. Arnold (eds.)3540525904, 9783540525905

This volume contains the proceedings of the Fifteenth Colloquium on Trees in Algebra and Programming. The papers selected present new research results and cover the following topics: – Logical, algebraic and combinatorial properties of discrete structures (strings, trees, graphs, etc.), including the theory of formal languages considered as that of sets of discrete structures and the theory of rewriting systems over these objects. – Application of discrete structures in computer science, including syntax and semantics of programming languages, operational semantics, logic programming, algorithms and data structures, complexity of algorithms and implementation aspects, proof techniques for nonnumerical algorithms, formal specifications, and visualization of trees and graphs.

---

Table of contents :
On the power of bounded concurrency II: The pushdown automata level….Pages 1-17
Trees everywhere….Pages 18-41
Combinatory forms for equational programming: Instances, unification and narrowing….Pages 42-56
Graphical versus logical specifications….Pages 57-71
More efficient bottom-up tree pattern matching….Pages 72-86
On the regular structure of prefix rewriting….Pages 87-102
A unified approach for showing language containment and equivalence between various types of ω -automata….Pages 103-116
Unitary monoid with two generators: An algorithmic point of view….Pages 117-131
Coherence of subsumption….Pages 132-146
Petri nets as models of linear logic….Pages 147-161
Towards the unification of models for concurrency….Pages 162-176
A markovian concurrency measure….Pages 177-190
Graph matching in operational semantics and typing….Pages 191-205
ML typability is dexptime-complete….Pages 206-220
Testing for inductiue (co)-reducibility….Pages 221-238
Probabilistic analysis of some distributed algorithms….Pages 239-253
Infinite values in hierarchical imperative types….Pages 254-268
Equivalence of finite-valued bottom-up finite state tree transducers is decidable….Pages 269-284