Although several generic process ontologies have been proposed in the past, the design of process ontologies for specific domains remains a challenge. Earlier work by Aameri that provided a methodology for specifying a domain process ontology requires a characterization of the partial automorphisms of the models of an underlying static domain ontology. In this paper, we exploit the modularization of domain ontologies as a means for reusing the existing domain process ontologies through ontology combination and merging. The metatheoretic relationships among ontologies within a repository play a key role in the characterization of how a domain process ontology for a given static domain is related to the domain process ontologies based on the different modules of the static domain ontology.
The design of ontologies which axiomatize classes of processes specific to a particular domain remains an important challenge in ontological engineering. A domain process ontology axiomatizes possible classes of change within the underlying domain, without enumerating the definable classes of activities. This distinguishes a process ontology from process descriptions and action theories, which axiomatize properties of specific activities. The focus is on domain process ontologies that only classify the atomic activities within a domain, those that characterize complex activities in the domain are more closely related to AI planning problems.
Aameri [
Suppose we need an ontology which axiomatizes sheet metal manufacturing
processes, and we utilize the CardWorld and BoxWorld ontologies, presented in [
As another example, suppose we want to axiomatize abstract data types and their
operations. Intuitively, we should be able to reuse the chains process ontology [
The focus of this paper is the presentation of formal techniques which address the idea of reusability and modularization in design and verification of domain process ontologies; in particular, we discuss how relationships between domain ontologies within an ontology repository can assist us in identifying the properties of ontologies’ models which are required in developing new domain process ontologies.
The concepts of reusability and modularization in the characterization of the models
of ontologies have been explored in [
We start by describing the general properties of domain process ontologies, and reviewing the methodology that Aameri proposed for designing such ontologies. In Section 3, we review the relationships between domain ontologies within a repository, and show how existing domain process ontologies can be reused in designing new domain process ontologies.
As we explained in the introduction, the objective in designing domain process
ontologies is to have a complete classification of activities based on their effects, without
enumerating all definable activity classes. By following the design methodology proposed in
[
The key idea behind the methodology is that all changes within a domain can be
described based on a fixed set of (primitive or defined) relations. If we identify those
relations and axiomatize activity classes that affect them, we can be sure that we have a
complete classification. For a given domain, the methodology designs a first-order process
ontology with three main modules – one is the ontology of the Process Specification
Language (PSL) [
The PSL ontology1 is a generic process ontology that axiomatizes fundamental concepts for describing processes. Within the PSL ontology, states are represented by the
Predicate activity(a) occurrence o f (o; a) prior(f; o) holds(f; o) changes(o; f)
Interpretation a is an activity. o is an occurrence of activity a.
Fluent f holds before activity occurrence o.
Fluent f holds after activity occurrence o. (:prior(f; o) ^ holds(f; o)) _ (prior(f; o) ^ :holds(f; o)).
Table 1. PSL Predicates set of fluents that hold before or after activity occurrences, and only activity occurrences can cause state transitions. A model of the PSL ontology includes partially ordered sets of activity occurrences, called occurrence trees. The root of an occurrence tree is associated with an initial state, and the branches are all sequences of occurrences of the atomic activities. Table 1 briefly describes PSL predicates that we use in this paper.
The methodology begins by identifying the appropriate domain ontology that axiomatizes the concepts of the underlying domain and their relationships independent of the notion of change. To enable reasoning about change, the axioms of the domain ontology are translated into a set of state constraints which extend the PSL ontology. Translation definitions map each relation symbol in the signature of the domain ontology into a fluent symbol in the signature of the state constraints. If the domain ontology is not sorted, the set of state constraints must contain an axiom which indicates sorts of the elements in the models of the domain ontology. The set of state constraints together with the PSL ontology is called domain state ontology.
The results in [
An injective mapping j : M1 ! M2 is a partial isomorphism loosed to a non-empty set L L iff for all relations R 2 L , hx1; : : : ; xni 2 RM1 iff hj (x1); : : : ; j (xn)i 2 RM2 :
A mapping j : M ! M is a loosed partial automorphism iff it is a loosed isomorphism between substructures of M .2
In general, a structure N can be represented by the set of all its partial
automorphisms denoted by PAut(N ). Note that PAut(N ) forms a monoid [
3We assume that for all o, the universes of m(o) and h(o) are equal; when an element is destroyed, it is
not annihilated from the universe. Rather, its sort will change from something that is indicated by the state
constraints to ob ject. Conversely, when an element is created a new sort is assigned to an ob ject of the universe.
can be represented by subsets of PAut(m(o)). Moreover, the results in [
A scaffold GoL of an activity occurrence o in M is a set consisting of all sets Gi such that 1. All Gi j 2 Gi are submonoids of PAutL(m(o)), such that their identity elements ei j are partial identities associated with invariant substructures (with respect to L) of m(o) and h(o); 2. The identity element ei j of each Gi j 2 Gi has a maximal domain; that is, there is no other identity mapping e0 that satisfies property 1 and dom(ei j) dom(e0); 3. If Gi = fGi1; : : : ; Gimg, then dom(ei1) [ [ dom(eim) dom(m(o)), and dom(ei1) \ \ dom(eim) = ?.
Activities can be categorized based on which fluents they change. However, since the objective is not to enumerate all activity classes, the methodology distinguishes the invariant substructures up to isomorphism, and more importantly, does not consider the number of fluents that activity occurrences change. The key question is how to identify a set of fluents that can describe all possible changes within the domain ontology? Suppose for two activity occurrences o1; o2, we have m(o1) = m(o2), but h(o1) 6= h(o2). Then, there is at least one fluent, denoted by the fluent symbol F, that o1 changes it, and o2 preserves it, and so GoF1 is not isomorphic to GoF2 . Therefore, the answer to the above question is equivalent to find the set CT defined in the following: Definition 3 Suppose a theory Tpsl [ Tst is the domain state ontology for a domain ontology T , and let L be the set of all primitive and definable symbols in the language of Tpsl [ Tst that correspond to the symbols in the language of T .
CT = fL1; :::; Lng, is the minimal set such that 1. L1 L; :::; Ln L; 2. for all activity occurrences o1; o2 in models of Tpsl [ Tst
m(o1) = m(o2); GoL11 = GoL21 ; :::; GoL1n = GoL2n implies h(o1) = h(o2).
For the chains ontology Tchains, we have CTchains = ffpointg; fltg; fcomparablegg
since a theorem in [
Definition 4 summarizes the properties of domain process ontologies that are designed with respect to the methodology. Considering property 2 in Definition 3, a complete classification includes an activity class for each element Li of CT such that the members of the class change fluents in Li. Thus, for each activity class the domain process ontology includes a definition that specifies which fluents are changed and which fluents are preserved by the members of the class. Since these definitions are in the signature (8a) change point(a) ((8o) occurrence o f (o; a) (9x) changes(o; point(x))): (8a) change lt(a) ((8o) occurrence o f (o; a) (9x; y) changes(o; lt(x; y))):
(8a) new chain(a) (change lt(a)^ (8o; x; y) (occurrence o f (o; a) ^ changes(o; lt(x; y))) changes(o; comparable(x; y))):
(8a) rearrange(a) (change lt(a)^ (8o; x; y) (occurrence o f (o; a) ^ changes(o; lt(x; y))) :changes(o; comparable(x; y))): (1) (2) (3) (4) of the underlying domain state ontology, the domain process ontology is a definitional extension of the domain state ontology. This is captured by property 1 in Definition 4.
Note that GoLi represents all changes that o makes to the fluents specified by symbols in Li. Therefore, if an activity class ci is associated with Li, the scaffolds that correspond to Li and the occurrences of the members of ci are nontrivial. On the other hand, when an activity is not a member of ci, its occurrences do not change fluents in Li, and so the corresponding scaffold is trivial. This is captured by property 2a in Definition 4.
Notice however that there might be constraints in the domain that enforce changing fluents in a set L j 2 CT whenever the fluents in Li 2 CT are changed. In that case, ci is a subclass of c j. Moreover, there are activities that change fluents in L j without changing the fluents in Li. An additional class is therefore required to distinguish these types of activities from activities in ci. For example, the fluent symbol comparable in Tchains is defined based on lt, and so any activity that changes comparable will also change lt. The activity class ccomparable is therefore a subclass of clt , and the chains process ontology (see Figure 1) includes a class of activities that change a fluent lt(a; b), but preserve comparable(a; b). Property 2b addresses this requirement.
Definition 4 Let Tpsl [ Tst be a domain state ontology for a domain ontology T .
Let l (Tprocess) = S(Tprocess) n S(Tpsl [ Tst ).
Tpsl [ Tst [ Tprocess is a domain process ontology for T iff 1. Tpsl [ Tst [ Tprocess is a definitional extension of Tpsl [ Tst such that for each ci 2 l (Tprocess) there is an axiom in Tprocess of the following form, (8a)ci(a) ((8o) occurrence o f (o; a)
Yi(o); where Yi(o) is a formula in the language of Tpsl [ Tst with a unique free variable o 2. Let Act(ci) = fa : hai 2 ciM g, where M 2 Mod(Tpsl [ Tst [ Tprocess), and SubClass(ci) = fAct(c j) : Act(c j) Act(ci)g.
There is an injective mapping j : CT ! l (Tprocess) such that (a) if ci = j (Li), then hai 2 ciM iff for all occurrences o of a, GoLi 6= Io. (b) if there is no Li 2 CT such that ci = j (Li), then exists c j = j (L j), such that
SubClass(c j) 6= ?, and Act(c j) n S SubClass(c j) Act(ci).
From this point forward, we will be using the phrase “domain process ontology” exclusively when referring to process ontologies that satisfy the properties specified by Definition 4.
Let o be an occurrence of an activity a which satisfies property 2 in Definition 3, but a is not a member of any activity class defined by the domain process ontology. According to the above definition, all scaffolds of o are trivial, and since o satisfies property 2, a has no effects in the underlying domain. In the other words, all nontrivial activities within a domain are members of at least one activity class defined by the respective domain process ontology. This implies that the classifications specified by domain process ontologies are complete.
A domain process ontology classifies activities and defines the corresponding hierarchy in such a way that classes in the leaves of the hierarchy tree includes activities that have same effects on isomorphic substructures of the respective domain. This ensures that the classification is neither enumerative, nor too general.
Theorem 1 proves these two important properties of domain process ontologies. Theorem 1 5 Let Tpsl [ Tst [ Tprocess be the domain process ontology for T , and c1; :::; cn be the activity classes defined in Tprocess.
1. Tpsl [ Tst [ Tprocess j= (8a)activity(a) c1(a) _ ::: _ cn(a); 2. Let a1; a2 be activities in a model M of Tpsl [ Tst [ Tprocess such that the effects of a1 and a2 on the isomorphic substructures of a model of T are not isomorphic. Then, either exists a leaf activity class ci in Tprocess such that ha1i 2 ciM and ha2i 62 ciM , or a1 and a2 are members of more than one leaf activity class.
The chains process ontology, for example, specifies a complete classification of possible activities, but does not enumerate all definable sets of activities. In the meantime, it is not too general as the members of each leaf activity class have same effects. To make this more clear, consider this example: let M 2 Mod(Tchains), where M = fx; yg, and hx; yi 2 ltM . Suppose a1 changes M to M1, where hy; xi 2 ltM1 , and a2 changes M to M2, where M2 = fx; yg, but hx; yi 62 ltM2 and hy; xi 62 ltM2 . Clearly, both a1 and a2 are members of change lt, however, this class is too general since a1 and a2 change isomorphic substructures of M , but have different effects. The chains process ontology resolves this problem by defining two subclasses, new chain and rearrange, for change lt.
In designing domain process ontologies we face two main challenges. First, we need to find the smallest set of fluent symbols C , that satisfies property 2 in Definition 3. Second, we have to identify the set of partial automorphisms for the relations that correspond to those fluents. For domains with more complex structures this is even harder, since the number of combinations that have to be examined with respect to property 2 increases exponentially. Fortunately, in practice we have found that elements (Li) of the fluents set C usually includes at most three fluent symbols. Therefore, in most cases we can find mathematical structures, with well-studied sets of partial automorphisms, that represent axioms that correspond to elements in Li. This would address the second challenge.
For the first challenge, one solution is to decompose the domain ontology into modules, determine the fluent set for each module, and then find the fluent set for the original 5Proofs of the theorems can be found at http://stl.mie.utoronto.ca/publications/reuseprocess.pdf ontology with respect to the fluent sets of its modules. In the following, we explore this idea further. We investigate three types of relationships among domain ontologies in a repository, namely extensions, synonymy and reducibility, and show how these relationships can help us in developing domain process ontologies.
We start by the simplest relationship between first-order ontologies.
extension of T1 iff for any sentence F in the language of T1, T1 j= F implies T2 j= F. T2 is a conservative extension of T1 iff T1 6j= F implies T2 6j= F.
Unfortunately, extension (or reduction) between domain ontologies is not preserved
between the corresponding domain process ontologies. The reason is that in classifying
activities, we consider partial symmetries between the models of the domain ontology
(partial symmetries are captured by partial automorphisms), while an arbitrary extension
might both increase or decrease partial symmetries among the models. However, we can
take advantage of extensions within the hierarchies of an ontology repository.
Definition 6 (from [
We know that T 0 T implies Mod(T ) Mod(T 0). That means that there might be axioms in the extension which excludes transitions to models that are related to a specific type of change, and so eliminates some of the activity classes of T 0. The extension might also change the definitions of the activity classes.
CT 0 .
Consider the ontology Tchains , and the ontology Tlinorder of linear orderings. Tlinorder is an extension of Tchains, and they are in the same hierarchy. As we described earlier, the chains process ontology includes three leaf activity classes, where the first class includes activities that create or destroy elements in the orderings, the second one includes activities which reorder elements in a single chain, and the third one is the set of activities that break a chain into a group of chains, or join a group of chains to make a single chain. However, the domain process ontology for Tlinorder only includes the first two classes since there is an axiom in Tlinorder which states that models of Tlinorder are single chains.
Recall that every constant, function, and relation in a model of a definitional extension of an ontology is definable in a model of the ontology. Consequently, every model of the ontology can be expanded to a unique model of its definitional extension, and two models of the ontology are isomorphic iff their expansions are isomorphic. This leads us to conclude that a domain ontology and all its definitional extensions share one single domain process ontology.
with the signature S(T1) [ S(T2) that is a definitional extension of T1 and T2.
Translation definitions are sentences that interpret non-logical symbols of an ontology, in the language of another ontology. It can be easily proved that for two synonymous ontologies T1 and T2, there exists a set of translation definitions D21 from T2 into T1 and a set of translation definitions D12 from T1 into T2 such that T1 [ D21 is logically equivalent to T2 [ D12. The other direction is true as well.
Definition 8 Let T0 and T1 be two ontologies such that S(T0) \ S(T1) = ?. Translation definitions for T0 into T1 are sentences in S(T0) [ S(T1) of the form 8x pi(x)
F(x); where pi(x) is a symbol in S(T0) and F(x) is a formula in the language of T1.
By definition, every pair of synonymous ontologies have a common definitional extension. Thus, the following theorem is an immediate consequence of Theorem 3.
Suppose two ontologies T1; T2 are synonymous, and the process ontology P1 for T1 already exists in the repository. We can translate the axioms of P1 into the language of T2, using D12, and the result is the process ontology for T2.
Consider the DOLCE direct quality ontology Tdir qual 6 (discussed in [
(9y) PD(y) ^ dqt(x; y) Using an automated theorem prover, it can be shown that Tdir qual is synonymous with the ontology of injection bipartite incidence structures Tin j bipartite7 under the following translation definitions (5) (6) (7) (8) (9) (10) (11) (12) (13) P : D : (8x; y) dqt(x; y)
in(x; y) ^ point(x) ^ line(y) (8x) T Q(x) (8x) PD(x)
dqt(x; y) _ dqt(y; x) _ x = y Therefore, the process ontology for Tdir qual can be achieved by translating Tin jbipart proc8, which is the process ontology for Tin j bipartite, into the language of Tdir qual using D. The result is depicted in Figure 2.9 6http://colore.oor.net/quality/direct%5Fquality.clif 7http://colore.oor.net/bipartite%5Fincidence/injection%5Fbipartite.clif 8http://colore.oor.net/injection%5Fbipartite%5Fprocess/definitions/injection%5Fbipartite%5Fprocess.clif 9http://colore.oor.net/direct%5Fquality%5Fprocess/definitions/direct%5Fquality%5Fprocess.clif (8a) change PD(a) ((8o) occurrence o f (o; a) (9x) changes(o; PD(x))): (8a) change quality(a) ((8o) occurrence o f (o; a) (9x; y) changes(o; dqt(x; y))): (15)
So far we have considered relationships between two ontologies. In the remaining of this
section, we investigate reusing domain process ontologies of theories that are
synonymous with the constructing modules of a domain ontology. We exploit the the notion
of faithful interpretation [
iff for all sentence F in the language of T1, T1 j= F implies T2 j= p (F). p is a faithful interpretation of T1 into T2 iff T1 6j= F implies T2 6j= p (F).
Synonymy is a relation between two ontologies. The notion of reducibility (from
[
2. T1 [ ::: [ Tn faithfully interprets T ; 3. T is synonymous with T1 [ ::: [ Tn.
The following lemma shows the construction of a domain process ontology from the domain process ontologies of the modules of the underlying domain ontology. Lemma 1 Suppose T = T1 [ ::: [ Tn is a consistent theory, and P; P1; :::; Pn are domain process schemata correspond to T; T1; :::; Tn respectively.
If S(Ti) \ S(Tj) = ?, for all 1 i; j n, then P = P1 [ ::: [ Pn.
Suppose in a reduction T1; :::; Tn for T , all modules except T1 and T2 have disjoint signatures. We can construct a new reduction T10; T3; :::; Tn for T , where T10 = T1 [ T2, so that the signatures of theories in the new reduction is disjoint. The following theorem, which is a consequence of Definition 10 and Theorem 4, shows the construction of the domain process ontology for T using the domain process ontologies of its disjoint reductive modules. Note that the domain process ontologies for T1 and T2 can be reused in constructing the domain process ontology for T1 [ T2.
Theorem 5 Suppose T is reducible to a set of ontologies T1; :::; Tn such that S(Ti) \ S(Tj) = ?, for 1 i; j n. Suppose P; P1; :::; Pn are domain process schemata correspond to T; T1; :::; Tn respectively.
Then P is synonymous with P1 [ ::: [ Pn.
Consider a version of the Blocks World problem, in which at most one block can be
placed on another, and each block has one unique color [
(8x; y; z)C(x; y; z) ((9l)line(l) ^ in(x; l) ^ in(y; l) ^ in(z; l)):
(8x; y; z; l) line(l) ^ in(x; l) ^ in(y; l) ^ in(z; l) ^ (x 6= y) ^ (x 6= z) ^ (y 6= z) (C(x; y; z) _C(z; y; x)):
(21)
(16)
(17)
(18)
(19)
For the bounded chains ontology, we reuse the verified chains process ontology from
[
Many ontologies are not reducible to standard mathematical ontologies, however, they have subtheories that are. These cases can be captured by the notion of weak reducibility.
2. T1 [ ::: [ Tn faithfully interprets a subtheory T 0 3. T 0 is synonymous with T1 [ ::: [ Tn.
T ;
The domain process ontologies of the reductive modules of a weakly reducible ontology T can be reused in designing the domain process ontology for the subtheory T 0 of T which is synonymous with the weak reduction. The new domain process ontology would be helpful in constructing the domain process ontology for T , as T and T 0 are in the same hierarchy and T is an extension of T 0.
Then CT CT 0 , where T 0 T and T 0 is synonymous with T1 [ ::: [ Tn.
Consider the ontology Tmcg12 of Megiddo cyclic geometries. Tmcg is weakly reducible to the ontology Tcyclic13 of cyclic orderings and the ontology Tweak bipart 14 of weak bipartite incidence geometries. Figure 3 shows the axioms of Tmcg that are not in Tcyclic and Tw bipart . The domain process ontologies for Tcyclic15 and Tw bipart 16 already exist in the repository, and so we know that CTcyclic = ffpointg; fCg; fcmpgg (where cmp(x; y; z) holds iff C(x; y; z) or C(z; y; x) hold) and CTw bipart = ffpointg; flineg; fingg. Consequently, we have CTmcg ff pointg; flineg; fing; fCg; fcmpgg. However, Axioms 11http://colore.oor.net/colored%5Fblocks%5Fprocess/definitions/colored%5Fblocks%5Fprocess.clif 12http://colore.oor.net/cyclic%5Fgeometry/mcg.clif 13http://colore.oor.net/cyclic%5Fordering/cyclic.clif 14http://colore.oor.net/bipartite%5Fincidence/weak%5Fbipartite.clif 15http://colore.oor.net/cyclic%5Fprocess/definitions/cyclic%5Fprocess.clif 16http://colore.oor.net/weak%5Fbipartite%5Fprocess/definitions/weak%5Fbipartite%5Fprocess.clif 20 and 21 prevent any changes in the fluent cmp without changing the fluent in, and therefore CTmcg = ffpointg; flineg; fing; fCgg. Theorem 7 formally proves this claim.17 Theorem 7 (MCG Classification Theorem) Suppose Tpsl [ Tstmcg is the domain state ontology for Tmcg, and M 2 Mod(Tpsl [ Tstmcg).
For any activity occurrences o1; o2 in M with m(o1) = m(o2), if Gop1oint = Gop2oint , Gloi1ne = Gloi2ne, Gion1 = Gion2 , GCo1 = GCo2 , then Gcom1p = Gcom2p, and consequently h(o1) = h(o2).
Decomposability is the weakest relation among the ontologies in a repository, but it can still assist us in developing domain process ontologies.
2. T1 [ ::: [ Tn faithfully interprets a subtheory T 0 3. T 0 is synonymous with T1 [ ::: [ Tn.
We can reuse the domain process ontologies of the reductive modules of a decomposable ontology in the same way as they are used for weakly reducible ontologies.
Then CT CT 0 , where T 0 T and T 0 is synonymous with T1 [ ::: [ Tn.
Consider the theory Trcc18 which axiomatizes the mereotopology Region Connection
Calculus (RCC) [
We know that CTBA = ffelementgg and CTconnection = ffCgg. Considering the translation definitions between Trcc and TBA, we can rename element to region, and therefore CTrcc ffregiong; fCgg. By the following theorem we have CTrcc = ffregiong; fCgg. 21 Theorem 9 (RCC Classification Theorem) Suppose Tpsl [ Tstrcc is the domain state ontology for Trcc, and M 2 Mod(Tpsl [ Tstrcc).
For any activity occurrences o1; o2 in M with m(o1) = m(o2), if Groe1gion = Groe2gion, GCo1 = GCo2 , then h(o1) = h(o2).
By designing a domain process ontology based on its underlying static domain ontology, we lay the foundations for the verification of the domain process ontology with respect to its intended models. Nevertheless, there is more to the evaluation of a domain process ontology than a characterization of its models. One of the challenges in designing process ontologies is to avoid the pitfall of enumerating all definable classes of activities while still showing that the classes in the ontology capture all of the necessary distinctions. To this end, we have provided a formal definition of a domain process ontology and have 17MCG process ontology: http://colore.oor.net/mcg%5Fprocess/definitions/mcg%5Fprocess.clif 18http://colore.oor.net/mereotopology/rcc.clif 19http://colore.oor.net/lattices/boolean%5Flattice.clif 20http://colore.oor.net/connections/connection.clif 21RCC process ontology: http://colore.oor.net/rcc%5Fcontinuous%5Fprocess/definitions/rcc%5Fprocess.clif shown that this enables us to prove the completeness of the classification specified by the ontology with respect to all possible changes within the domain.
A second challenge is that the methodology for designing process ontologies also requires a characterization of the partial automorphisms of the models that represent the underlying domain, and such a characterization is not known in many cases. To overcome this difficulty, we have proposed techniques for using the decomposition of the ontologies into modules, identifying the partial automorphisms of the models of these modules, and then using this information to build the process ontology. Furthermore, we applied these techniques to design three new domain process ontologies to demonstrate the feasibility of the approach.
In developing formal ontologies, reusability is exploited in different forms; existing
ontologies can be imported, extended, specialized, combined [
All of these process ontologies have been designed by starting with some existing domain ontology (such as orderings, geometries, or mereotopology). In practice, there also exist taxonomies of process classes that are part of upper ontologies or ontologies for areas such as chemical pathways and manufacturing. In these cases, there is no explicit static domain ontology which was used in the design of the taxonomies. Future work will need for evaluating such process taxonomies through the identification of the correct static domain ontology.