Caap '92: 17th Colloquium on Trees in Algebra and Programming Rennes, France, February 26-28, 1992. Proceedings

ISBN-13: 9783540552512 / Angielski / Miękka / 1992 / 491 str.

Jean-Claude Raoult; J. -C Raoult

Opis

This is a selection of 19 papers from a joint 1992 CAAP/ESOP (Colloquium on Trees in Algebra and Programming/ European Symposium on Programming) meeting, which covers discrete data structures (graphs, equations, transformations of graphs), and their links with logical computing theories (material extended from CAAP's original work on algebraic and combinatorial properties of trees).

Spis treści

A constructive valuation interpretation for classical logic and its use in witness extraction.- Varieties of increasing trees.- Origin functions in ?-calculus and term rewriting systems.- An algebraic approach to the interpretation of recursive types.- Decidability of reachability and disjoint union of term rewriting systems.- A complete type inference algorithm for simple intersection types.- Monadic second-order definable graph transductions.- CTL* and ECTL* as fragments of the modal ?-calculus.- Power domains supporting recursion and failure.- Parallel contraction of fibonacci trees and prefix computations on a family of interconnection topologies.- Must preorder in non-deterministic untyped ?-calculus.- A programming language for deriving hypergraphs.- Graph grammars as context-dependent rewriting systems: A partial ordering semantics.- Empty stack Pushdown ?-tree automata.- Modulo counting quantifiers over finite trees.- Finite tree automata with cost functions.- Partial type assignment in left linear applicative term rewriting systems.- A linear algorithm for solving fixed-point equations on transition systems.- Beyond conditional equations.