Trees in Algebra and Programming — CAAP’94: 19th International Colloquium Edinburgh, U.K., April 11–13, 1994 Proceedings

Hubert Comon, Ralf Treinen (auth.), Sophie Tison (eds.)354057879X, 9783540578796

This volume contains the papers selected for presentation at the 19th Colloquium on Trees in Algebra and Programming (CAAP ’94), which was held jointly with the fifth European Symposium on Programming (ESOP ’94) in Edinburgh in April 1994. Originally this colloquium series was devoted to the algebraic and combinatorial properties of trees, and their role in various fields of computer science. Taking into account the evolution of computer science, CAAP ’94 focuses on logical, algebraic and combinatorial properties of discrete structures (strings, trees, graphs, etc.); the topics also include applications to computer science provided that algebraic or syntactic methods are involved. The volume contains 21 papers selected from 51 submissions as well as two invited papers.

---

Table of contents :
Ordering constraints on trees….Pages 1-14
Graph grammars and tree transducers….Pages 15-36
Type Preorders….Pages 37-51
Compilative constructive negation in constraint logic programs….Pages 52-67
A new linear algorithm for Modular Decomposition….Pages 68-84
A CPS-translation of the λμ-calculus….Pages 85-99
A lower bound on the growth of functions computed by tree transductions….Pages 100-114
On the decidability of model checking for several μ-calculi and Petri nets….Pages 115-129
Generalizations of the periodicity theorem of Fine and Wilf….Pages 130-141
Probabilistic domains….Pages 142-156
Some results on top-context-free tree languages….Pages 157-171
On higher order recursive program schemes….Pages 172-186
Graphs and decidable transductions based on edge constraints….Pages 187-201
Nondeterministic automata with concurrency relations and domains….Pages 202-217
Algebraic and combinatorial properties of simple, coloured walks….Pages 218-233
Probabilistic analysis of an election algorithm in a tree….Pages 234-245
On the first-order equivalence of call-by-name and call-by-value….Pages 246-260
On the modularity of confluence of constructor-sharing term rewriting systems….Pages 261-275
Global program analysis in constraint form….Pages 276-290
On projective and separable properties….Pages 291-307
A rank hierarchy for deterministic tree-walking transducers….Pages 308-321
Superposition in picture languages….Pages 322-334
A grammar-based data-flow analysis to stop deforestation….Pages 335-351