Caap '92: 17th Colloquium On Trees In Algebra And Programming Rennes, France, February 26-28, 1992. Proceedings (lecture Notes In Computer Science)

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. 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

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.

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 in this volume