CAAP '92

1. Front Matter

   PDF

2. A constructive valuation interpretation for classical logic and its use in witness extraction

   • Franco Barbanera, Stefano Berardi

   Pages 1-23

3. Varieties of increasing trees

   • François Bergeron, Philippe Flajolet, Bruno Salvy

   Pages 24-48

4. Origin functions in λ-calculus and term rewriting systems

   • Yves Bertot

   Pages 49-65

5. An algebraic approach to the interpretation of recursive types

   • Felice Cardone

   Pages 66-85

6. Decidability of reachability and disjoint union of term rewriting systems

   • Anne -Cécile Caron

   Pages 86-101

7. A complete type inference algorithm for simple intersection types

   • M. Coppo, P. Giannini

   Pages 102-123

8. Monadic second-order definable graph transductions

   • Bruno Courcelle

   Pages 124-144

9. CTL* and ECTL* as fragments of the modal μ-calculus

   • Mads Dam

   Pages 145-164

10. Power domains supporting recursion and failure

    • Reinhold Heckmann

    Pages 165-181

11. Parallel contraction of fibonacci trees and prefix computations on a family of interconnection topologies

    • W. -J. Hsu, C. V. Page, J. Liu

    Pages 182-202

12. Must preorder in non-deterministic untyped λ-calculus

    • U. De'Liguoro, A. Piperno

    Pages 203-220

13. A programming language for deriving hypergraphs

    • Andrea Maggiolo-Schettini, Józef Winkowski

    Pages 221-231

14. Graph grammars as context-dependent rewriting systems: A partial ordering semantics

    • Ugo Montanari, Francesca Rossi

    Pages 232-247

15. Empty stack Pushdown ω-tree automata

    • Wuxu Peng, S. Purushothaman

    Pages 248-264

16. Modulo counting quantifiers over finite trees

    • Andreas Potthoff

    Pages 265-278

17. Finite tree automata with cost functions

    • Helmut Seidl

    Pages 279-299

18. Partial type assignment in left linear applicative term rewriting systems

    • Steffen van Bakel, Sjaak Smetsers, Simon Brock

    Pages 300-321

19. A linear algorithm for solving fixed-point equations on transition systems

    • Bart Vergauwen, Johan Lewi

    Pages 322-341

20. Beyond conditional equations

    • Uwe Wolter, Michael Löwe

    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.

• Conditional Equations
• Diskrete Strukturen
• Logics and Formal languages
• Logik und Formale Sprachen
• Programmiersysteme
• Programming Systems
• Specification Techniques
• Spezifikationstechniken
• Topologie
• algorithm
• algorithms
• automata
• logic
• programming
• programming language
• algorithm analysis and problem complexity

Policies and ethics