CAAP ’92: 17th Colloquium on Trees in Algebra and Programming Rennes, France, February 26–28, 1992 Proceedings

Franco Barbanera, Stefano Berardi (auth.), J. -C. Raoult (eds.)3540552510, 9783540552512

This volume contains selected papers presented at the seventeenth Colloquiumon Trees in Algebra and Programming (CAAP) held jointly with the European Symposium on Programming (ESOP) in Rennes, France, February 26-28, 1992 (the proceedings of ESOP appear in LNCS 582). The previous colloquia were held in France, Italy, Germany, Spain, Denmark and England. Every even year, as in 1992, CAAP is held jointly with ESOP; every other year, it is part of TAPSOFT (Theory And Practice of SOFTware development). In the beginning, CAAP was devoted to algebraic and combinatorial properties of trees and their role in various fields of computer science. The scope of CAAP has now been extended to other discrete structures, like graphs, equations and transformations of graphs, and their links with logical theories. The programme committee received 40 submissions, from which 19 papers have been selected for inclusion inthis volume.

---

Table of contents :
A constructive valuation interpretation for classical logic and its use in witness extraction….Pages 1-23
Varieties of increasing trees….Pages 24-48
Origin functions in λ-calculus and term rewriting systems….Pages 49-65
An algebraic approach to the interpretation of recursive types….Pages 66-85
Decidability of reachability and disjoint union of term rewriting systems….Pages 86-101
A complete type inference algorithm for simple intersection types….Pages 102-123
Monadic second-order definable graph transductions….Pages 124-144
CTL * and ECTL * as fragments of the modal μ-calculus….Pages 145-164
Power domains supporting recursion and failure….Pages 165-181
Parallel contraction of fibonacci trees and prefix computations on a family of interconnection topologies….Pages 182-202
Must preorder in non-deterministic untyped λ-calculus….Pages 203-220
A programming language for deriving hypergraphs….Pages 221-231
Graph grammars as context-dependent rewriting systems: A partial ordering semantics….Pages 232-247
Empty stack Pushdown ω-tree automata….Pages 248-264
Modulo counting quantifiers over finite trees….Pages 265-278
Finite tree automata with cost functions….Pages 279-299
Partial type assignment in left linear applicative term rewriting systems….Pages 300-321
A linear algorithm for solving fixed-point equations on transition systems….Pages 322-341
Beyond conditional equations….Pages 342-361