Trees and Semantics

Christel BaierChristel Baier

DOI Link

Christel Baier
Trees and Semantics
Theoretical Computer Science, 179(1-2):217--250, 1997

Details
Bibtex

KurzfassungAbstract
Several types of trees are proposed in the literature to model the behaviour of nondeterministic processes. The purpose of this paper is to clarify the distinction between the various types of trees and to discuss their use as semantic domains. Trees (in the sense of Milner's derivation trees) and bisimulation equivalence classes of trees are considered in three different settings: in the category of sets, in the metric setting and in the partial order setting. Each type of tree is characterized by a domain equation. Special attention is given to the use of trees as models for processes which allow for unbounded nondeterminism as for instance Milners CCS processes. In this case one has to deal with infinitely branching trees which cause problems to give denotational semantics that are fully abstract w.r.t. a transition system based operational semantics.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@article{B1997,
  author  = {Christel Baier},
  title   = {Trees and Semantics},
  journal = {Theoretical Computer Science},
  volume  = {179},
  number  = {1-2},
  year    = {1997},
  pages   = {217--250},
  doi     = {10.1016/S0304-3975(96)00107-7}
}