Occurrence Trees

Occurrence Trees

An occurrence tree is the set of all discrete sequences of activity occurrences. They are isomorphic to substructures of the situation tree from situation calculus, the primary difference being that rather than a unique initial situation, each occurrence tree has a unique initial activity occurrence. As in the situation calculus, the poss relation is introduced to allow the statement of constraints on activity occurrences within the occurrence tree. Since the occurrence trees include sequences that modellers of a domain will consider impossible, the poss relation "prunes" away branches from the occurrences tree that correspond to such impossible activity occurrences.

It should be noted that the occurrence tree is not the structure that represents the occurrences of subactivities of an activity. The occurrence tree is not representing a particular occurrence of an activity, but rather all possible occurrences of all activities in the domain.

The basic ontological commitments of the Occurrence Tree Theory are based on the following intuitions:

Intuition 1:

An occurrence tree is a partially ordered set of activity occurrences, such that for a given set of activities, all discrete sequences of their occurrences are branches of the tree.

An occurrence tree contains all occurrences of all activities; it is not simply the set of occurrences of a particular (possibly complex) activity. Because the tree is discrete, each activity occurrence in the tree has a unique successor occurrence of each activity.

Intuition 2:

There are constraints on which activities can possibly occur in some domain.

This intuition is the cornerstone for characterizing the semantics of classes of activities and process descriptions. Although occurrence trees characterize all sequences of activity occurrences, not all of these sequences will intuitively be physically possible within the domain. We will therefore want to consider the subtree of the occurrence tree that consists only of possible sequences of activity occurrences; this subtree is referred to as the legal occurrence tree.

The definitional extensions of the PSL Ontology use different constraints on possible activity occurrences as a way of classifying activities.

Intuition 3:

Every sequence of activity occurrences has an initial occurrence (which is the root of an occurrence tree).

This intuition is closely related to the properties of occurrence trees. For example, one could consider occurrences to form a semilinear ordering (which need not have a root element) rather than a tree (which must have a root element). However, we are using occurrence trees to characterize the semantics of different classes of activities, rather than using the occurrence tree to represent history (which may not have an explicit initial event). In our case, it is sufficient to consider all possible interactions between the set of activities in the domain, and we lose nothing by restricting our attention to initial occurrences of the activities. For example, given the query "Can the factory produce 1000 widgets by Friday?", one can take the initial state to be the current state, and the initial activity occurrences being the activities that could be performed at the current time.

Intuition 4:

The ordering of activity occurrences in a branch of an occurrence tree respects the temporal ordering.

Within the theory of occurrence trees, the ordering over activity occurrences and the ordering over timepoints are distinct. The set of activity occurrences is partially ordered (hence the intuition about occurrence trees), but timepoints are linearly ordered (since this theory is an extension of PSL-Core). However, every branch of an occurrence tree is totally ordered, and the intuition requires that the beginof timepoint for an activity occurrence along a branch is before the beginof timepoints of all following activity occurrences on that branch.


Informal Semantics for Occurrence Trees

(initial ?occ) is TRUE in an interpretation of the Occurrence Tree Theory if and only if the activity occurrence ?occ is a root of the occurrence tree.

(earlier ?occ1 ?occ2) is TRUE in an interpretation of the Occurrence Tree Theory if and only if the two activity occurrences ?occ1 and ?occ2 are on the same branch of the tree and ?occ1 is closer to the root of the tree than ?occ2. In other words, the earlier relation specifies the partial ordering over the activity occurrences in this tree.

(= (successor ?a ?occ) ?occ2) is TRUE in an interpretation of the Occurrence Tree Theory if and only if ?occ2 denotes the occurrence of ?a that follows consecutively after the activity occurrence ?occ in the occurrence tree.

(arboreal ?s) is TRUE in an interpretation of the Occurrence Tree Theory if and only if ?s is an element of the occurrence tree.

(generator ?a) is TRUE in an interpretation of the Occurrence Tree Theory if and only if ?a is an activity whose occurrences are elements of the occurrence tree.

(legal ?occ) is TRUE in an interpretation of the Occurrence Tree Theory if and only if the activity occurrence ?occ is an element of the legal occurrence tree.

(poss ?a ?occ) is TRUE in an interpretation of the Occurrence Tree Theory if and only if the activity ?a can possibly occur after the activity occurrence ?occ.

(precedes ?occ1 ?occ2) is TRUE in an interpretation of the Occurrence Tree Theory if and only if the activity occurrence ?occ1 is earlier than the activity occurrence ?occ2 in the occurrence tree and such that all activity occurrences between them correspond to activities that are possible. This relation specfies the sub-tree of the occurrence tree in which every activity occurrence is the occurrence of an activity that is possible


Axioms for Occurrence Trees


Last Updated: Wednesday, 15-December-2003 11:42:40

Return to the PSL homepage