Hostname: page-component-76fb5796d-qxdb6 Total loading time: 0 Render date: 2024-04-26T16:55:59.115Z Has data issue: false hasContentIssue false

Observational trees as models for concurrency

Published online by Cambridge University Press:  01 December 1999

STEFANO KASANGIAN
Affiliation:
Dip. di Matematica, Università di Milano, Italy
ANNA LABELLA
Affiliation:
Dip. di Scienze dell'Informazione, Università di Roma ‘La Sapienza’, Italy

Abstract

Given an automaton, its behaviour can be modelled as the sets of strings over an alphabet A that can be accepted from any of its states. When considering concurrent systems, we can see a concurrent agent as an automaton, where non-determinism derives from the fact that its states can offer a different behaviour at different moments in time. Non-deterministic computations between a pair of states can then no longer be described as a ‘set’ of strings in a free monoid. Consequently, between two states we will have a labelled structured set of computations, where the structure describes the possibility of two computations parting from each other while maintaining the same observable steps. In this paper, we shall consider different kinds of observation domains and related structured sets of computations. Structured sets of computations will be organised as a category of generalised trees built over a meet-semilattice monoid formalizing the observation domain. Theorems allowing us to introduce the usual concurrency operators in the models and relating different models will then be obtained by first considering ordinary functors (on and between the observation domains), and then lifting them to the categories of structured sets of computations.

Type
Research Article
Copyright
1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)