CAAP '90

1. Front Matter

   PDF

2. On the power of bounded concurrency II: The pushdown automata level

   • Tirza Hirst, David Harel

   Pages 1-17

3. Trees everywhere

   • Xavier Gérard Viennot

   Pages 18-41

4. Combinatory forms for equational programming: Instances, unification and narrowing

   • M. Bellia, M. Bugliesi, M. E. Occhiuto

   Pages 42-56

5. Graphical versus logical specifications

   • Gérard Boudol, Kim G. Larsen

   Pages 57-71

6. More efficient bottom-up tree pattern matching

   • J. Cai, R. Paige, R. Tarjan

   Pages 72-86

7. On the regular structure of prefix rewriting

   • Didier Caucal

   Pages 87-102

8. A unified approach for showing language containment and equivalence between various types of ω-automata

   • E. M. Clarke, I. A. Browne, R. P. Kurshan

   Pages 103-116

9. Unitary monoid with two generators: An algorithmic point of view

   • M. Crochemore, J. Neraud

   Pages 117-131

10. Coherence of subsumption

    • Pierre-Louis Curien, Giorgio Ghelli

    Pages 132-146

11. Petri nets as models of linear logic

    • Uffe Engberg, Glynn Winskel

    Pages 147-161

12. Towards the unification of models for concurrency

    • Gian Luigi Ferrari, Ugo Montanari

    Pages 162-176

13. A markovian concurrency measure

    • Dominique Geniet, René Schott, Loÿs Thimonier

    Pages 177-190

14. Graph matching in operational semantics and typing

    • Kristoffer Høgsbro Holm

    Pages 191-205

15. ML typability is dexptime-complete

    • A. J. Kfoury, J. Tiuryn, P. Urzyczyn

    Pages 206-220

16. Testing for inductiue (co)-reducibility

    • Emmanuel Kounalis

    Pages 221-238

17. Probabilistic analysis of some distributed algorithms

    • G. Louchard, R. Schott

    Pages 239-253

18. Infinite values in hierarchical imperative types

    • Michael I. Schwartzbach

    Pages 254-268

19. Equivalence of finite-valued bottom-up finite state tree transducers is decidable

    • Helmut Seidl

    Pages 269-284

20. Back Matter

    PDF

This volume contains the proceedings of the Fifteenth Colloquium on Trees in Algebra and Programming. The papers selected present new research results and cover the following topics: - Logical, algebraic and combinatorial properties of discrete structures (strings, trees, graphs, etc.), including the theory of formal languages considered as that of sets of discrete structures and the theory of rewriting systems over these objects. - Application of discrete structures in computer science, including syntax and semantics of programming languages, operational semantics, logic programming, algorithms and data structures, complexity of algorithms and implementation aspects, proof techniques for nonnumerical algorithms, formal specifications, and visualization of trees and graphs.

• algebra
• algorithm
• algorithms
• complexity
• data structure
• data structures
• formal language
• formal specification
• logic
• programming
• programming language
• semantics
• sets

Policies and ethics