Trees in Algebra and Programming — CAAP ’96: 21st International Colloquium Linköping, Sweden, April 22–24, 1996 Proceedings

Samson Abramsky (auth.), Hélène Kirchner (eds.)3540610642, 9783540610649

This book constitutes the refereed proceedings of the 21st International Colloquium on Trees in Algebra and Programming, CAAP ’96, held in Linköping, Sweden, in April 1996.
The 21 full revised papers presented were selected from 44 submissions; also included are invited papers by Samson Abramsky and Frank Pfenning. In keeping with the tradition of the CAAP conferences, this volume covers algebraic, logical, and combinatorial properties of discrete structures and their application to computer science, in particular to the theory of computation and to programming theory.

---

Table of contents :
Semantics of interaction….Pages 1-1
The Kronecker product and local computations in graphs….Pages 2-16
Iterative pairs and multitape automata….Pages 17-29
Diophantine equations, Presburger arithmetic and finite automata….Pages 30-43
A pumping lemma for output languages of macro tree transducers….Pages 44-58
The area determined by underdiagonal lattice paths….Pages 59-71
Extraction of concurrent processes from higher dimensional automata….Pages 72-86
Axiomatising extended computation tree logic….Pages 87-101
Final semantics for a higher order concurrent language….Pages 102-118
The practice of logical frameworks….Pages 119-134
Subsumption algorithms based on search trees….Pages 135-148
Interaction nets and term rewriting systems (extended abstract)….Pages 149-164
Computing in unpredictable environments: Semantics, reduction strategies, and program transformations….Pages 165-179
Relative normalization in Deterministic Residual Structures….Pages 180-195
Termination by absence of infinite chains of dependency pairs….Pages 196-210
Confluence without termination via parallel critical pairs….Pages 211-225
An ordinal calculus for proving termination in term rewriting….Pages 226-240
Behavioural satisfaction and equivalence in concrete model categories….Pages 241-256
Open maps, behavioural equivalences, and congruences….Pages 257-271
Denotational, causal, and operational determinism in event structures….Pages 272-286
Effective longest and infinite reduction paths in untyped λ-calculi….Pages 287-301
Full abstraction for lambda calculus with resources and convergence testing….Pages 302-316
Untyped lambda-calculus with input-output….Pages 317-329