Temporal Semantics of Complex Reasoning Tasks

Frances Brazier, Jan Treur, Niek Wijngaards and Mark Willems

Artificial Intelligence Group,
Department of Mathematics and Computer Science,
Vrije Universiteit Amsterdam,
De Boelelaan 1081a,
1081 HV Amsterdam, The Netherlands
Email: {frances, treur, niek, willems}@cs.vu.nl
URL: http://www.cs.vu.nl/~wai

Abstract A formal approach to modelling and specifying complex dynamic tasks is introduced. A basic assumption is that complex (reasoning) tasks can be modelled by a compositional architecture wherein (sub-)components correspond to (sub-)tasks. Explicitation of the control of a system's behaviour is essential when modelling complex reasoning tasks. A modelling framework is presented including a language for the specification of compositional architectures. The semantics is a description of a compositional system's behaviour, and a temporal approach provides a means to describe the dynamics involved. Temporal models are used to formalise this semantics. The compositional structure of information states, transitions and reasoning traces provides a transparant model of the system's behaviour, both conceptually and formally.


Complex tasks in which reasoning plays an important role, such as design and decision tasks, are most often extremely dynamic. The behaviour exhibited by (design and decision) systems is the result of interaction between (autonomous) agents and the material world. Non-monotonic behaviour is the rule rather than the exception.

The aim in knowledge engineering is to model such complex behaviour. The common approach is to model complex functionality by means of task (de)composition; where a complex task at a certain level comprises of subtasks and task control at a lower level. Non-monotonic behaviour modelled in this way naturally leads to a view of behaviour as sequences of states (of eventually monotonic subtasks) over time. A system, for example, can explicitly reason about its own behaviour on the basis of which it can influence its own control of its behaviour: in fact temporal reasoning.

Within knowledge engineering the ability to formally describe the behaviour of models (of complex tasks) contributes to the modelling, design, evaluation and maintenance, validation and verification, and reuse of components (of models of knowledge-based systems) (Harmelen and Fensel, 1995). As such, formal methods provide a means to formally describe a complex task thereby providing a common ground for informal models of the same complex task.

A framework that allows conceptual and formal specification of such models should be powerful enough to capture such behaviour in an explicit and transparant manner. A number of the current approaches to modelling complex reasoning tasks, in which formal specification plays an important role, are MIKE/KARL, KADS/(ML)2, and MILORD (Fensel, 1993; Akkermans, Harmelen, Schreiber, and Wielinga, 1992; Agusti, Esteva, Carcia, Godo, de Mantaras, Murgui, Puyol, and Sierra, 1992; Fensel and Harmelen, 1994; Treur and Wetter, 1993). These frameworks include a formal syntax for the specification language, but the formal semantics of such systems from a temporal perspective is often not defined.

Especially for compositional dynamic tasks, both a conceptual and formal definition of the temporal semantics of behaviour is of importance. Formal semantics not only provides a basis for validation and verification of system behaviour, but specifications of components at different levels of abstraction with well-defined semantics also provide a means to enable automated support for redesign of task models and components (Brazier, Langen, Treur, and Wijngaards, 1996). Automated support for redesign, for example, often requires explicit formulation of requirements on system behaviour. In this paper the formal approach to modelling dynamic reasoning tasks within compositional architectures, DESIRE (Langevelde, Philipsen, and Treur, 1992; Brazier, Treur, Wijngaards, and Willems, 1995), and its temporal semantics is extended to include hierarchical decomposition.

Section 2 provides an overview of the knowledge modelled and specified in task models. In Section 3 the perspective on temporal semantics is introduced and the basic concepts are defined. In Section 4 definitions of the concepts required to formalise compositional information states are introduced, followed by definitions of concepts directly related to transitions between (hierarchical) component information states in Section 5. The formalisation of the resulting compositional behaviour is defined in terms of the temporal approach in Section 5 and discussed in Section 6. Further discussion of applications for which this approach has been successfully applied extends beyond the scope of this paper: see, for example (Brazier, Dunin-Keplicz, Jennings, and Treur, 1995; Brazier, Langen, Ruttkay, and Treur, 1994; Brazier and Treur, 1994; Geelen and Kowalczyk, 1992).


To acquire specifications of complex (reasoning) systems extensive interaction between knowledge engineers and experts is required. The purpose of such interaction, within DESIRE, is to acquire a shared (agreed) task model: a model on which both the knowledge engineers and the experts agree (Brazier, Treur, and Wijngaards, 1996). Existing task models, usually generic task models, are most often used to initially structure knowledge acquisition. Which models are used, depends on the initial description of a task or task components: in interaction with one or more experts existing models are examined, discussed, rejected, modified, refined and/or instantiated. Such task models are generic in two senses: they are a description of the task both at an abstract level and application domain independent. Initial abstract descriptions of tasks can be used to generate a variety of more specific task descriptions through refinement and composition (existing descriptions can be employed) in interaction with experts. During knowledge acquisition knowledge of the application domain itself is also acquired: such application specific knowledge is modelled independently in knowledge structures, and is included in task models by reference to such structures. Knowledge structures are also shared models: models of the domain. Which techniques are used for knowledge elicitation is not predefined. Techniques vary in their applicability, depending on the situation, the resources, the task, the type of knowledge on which the knowledge engineer wishes to focus, etc.

A shared task model is, in fact, a mediating model. It mediates between a knowledge engineer and an expert, but also between a knowledge engineer and system design. Within the DESIRE framework task models provide the basis for system architecture. Tasks are mapped onto components, subtasks onto subcomponents, interactions between tasks are mapped onto information links between components. Domain knowledge is mapped onto structures which are referenced in specifications of components. The goals pursued and the roles of the parties involved in relation to the goals are defined. A description of the situation in which such goals can be pursued, and of the assumptions with respect to task performance are made explicit.

The result of task analysis is a conceptual specification of five types of knowledge:

2.1 Task decomposition

Task decomposition includes knowledge of a task hierarchy (tasks and subtasks), knowledge of the types of information required as input and resulting as output, and knowledge of the reflective nature of tasks with respect to other tasks.

A task hierarchy defines which subtasks of the task are distinguished and the task-subtask relations between them. This entails a one-to-many relation which, for example, can be specified by means of a table (not shown) and depicted as a tree structure or a box-in-box structure (see Figures 1 and 2).

Figure 1: Pictoral specifications of a task decomposition.

In the task model for an elevator configuration task (Brazier, Langen, Treur, Wijngaards, and Willems, 1996), 'requirement extension determination' proposes extensions to the current set of requirement parameters. It proposes values for requirement parameters that do not have a value yet; adding this value extends the requirement parameters set. 'Extension suitability determination' determines which requirement parameters are best suited to be given a value. 'Extension method determination' decides which method to use to determine a value for the chosen requirement parameter: by means of default reasoning or user consultation. 'Default requirement determination' assigns a value to the chosen requirement parameter, and 'user requirement acquisition' obtains a value by interacting with the user, and assigns the value to the chosen parameter.

The task of 'extension suitability determination' is decomposed into three subtasks, of which the task 'determine non-candidate parameters' finds out which parameters are not a candidate for extension, the task 'make assumptions on candidate parameters' employs a closed-world-assumption to determine which candidate parameters are still eligible for extension, and the task 'determine parameter suitable for extension' selects one of these eligible parameters as suitable parameter. This example illustrates a non-monotonic task realized by a combination of monotonic subtasks. The task of 'extension suitability determination' is non-monotonic as it does not conserve its output when more input is available (not retracting already known input).

Conceptually, for each task, the types of information required as input or generated as output of a task should be specified. This can be done by defining names for information types (names chosen by the knowledge engineer and the expert(s)) and relations expressing how such information is related to a tasks' output and/or input. In a pictoral representation, each (sub)task can be annotated with information regarding the types of information of its input and output, for example, with input to the left and output to the right as shown in Figure 2.

Figure 2: Input & output types of information of task 'extension suitability determination'.

The reflective nature of tasks is another important element of the task decomposition that is emphasised in DESIRE. Essential for a transparant specification of a system is a clear distinction between object-level reasoning about some domain, from meta-level reasoning about the state and goals of a system. This object-meta distinction between tasks can be specified explicitly as an object-meta relation, an example is shown in Table 1.


with respect to
determine non
candidate parameters

make assumptions on candidate parameters
determine parameters
suitable for extension

make assumptions on candidate parameters

Table 1. Object-meta distinction between tasks

2.2 Information exchange between (sub-)tasks

Knowledge of information exchange between (sub-)tasks defines the types of information transferred between (sub-)tasks. More specifically, the relations expressing information exchange between tasks are explicitly specified. Moreover, it can be useful to introduce names for these possible transfers of information, in particular to control the information flow (see Section 2.3).

Figure 3: Information exchange among subtasks and between subtasks and the task of 'extension suitability determination'.

In Figure 3 examples of two kinds of relations are shown in a pictoral representation: private information exchange between the output information type of one subtask and the input information type of another subtask, and mediating information exchange between the output information type of a subtask and the output information type of its task (and vice versa).

Not only are the types of information to be transferred from one (sub-)task to the next (sub-)tasks defined, but also the grounds upon which the 'decision' to forward this information. Explicit evaluation criteria are specified for this purpose. They are discussed in next subsection.

2.3 Task sequencing

Knowledge of sequencing of task and information exchange defines temporal relations between (sub-)tasks (and information transfer): which tasks must (directly) precede other tasks and which information exchange is required. Task sequencing knowledge specifies under which conditions which tasks and information flows follow which other tasks. These conditions, preconditions for task activation, may, for example, include evaluation criteria expressed in terms of the evaluation of the results (success or failure) of one or more of the preceding tasks (and do not include the actual results). The evaluation criteria, the result and the name of the next task(s) to be activated can be specified in an (incomplete) pictoral representation where 'control' arrows are labeled with the evaluation criteria (- for failure and + for success), as shown in figure 4, for example:

Fig 4. Pictoral representation of task sequencing in 'extension suitability determination'.
In addition (or alternatively) general knowledge of task sequencing may be available: knowledge of which tasks may be performed in parallel and which tasks must precede which other tasks (not necessarily directly nor conditionally). Current research focusses on suitable representations.

2.4 Role delegation

In complex situations often a number of autonomous systems and/or users are involved. Even in a traditional view of (knowledge-based) systems, the user and system interact to achieve the necessary behaviour. Knowledge of role delegation refers to the division of tasks amongst participants: minimally which tasks are to be performed by the system and which by one or more users. In more complex situations often more participants are involved. Essentially role delegation is defined by a set of participants (i.e. agents) and a relation between tasks and subsets of the set of agents. See Table 2 for an example.


RQS Extension Determination
System, User
Extension Suitability Determination
Extension Method Determination
Default Requirement Determination
User Requirement Acquisition
Determine Non-Candidate Parameters
Make Assumptions on Candidate Parameters
Determine Parameters Suitable for Extension

Table 2: Role delegation of tasks of 'RQS Extension Determination'

A pictoral representation can be obtained by placing the (sets of) agents in the tree representing the task hierarchy.

2.5 Knowledge structures and relation to tasks

Knowledge of knowledge structures entails specification of the types of knowledge which are needed for task performance: for input and output information structures but also internal knowledge bases used for reasoning. For each task the names of information types and knowledge bases are related to the task(s) that refer(s) to them, as shown in an example below.


information type
knowledge base
Determine Non-Candidate Parameters
Det-Non-Cand-Param Info Type
Determine Non-Candidate Parameters Knowledge
Make Assumptions on Candidate Parameters
Make-Ass-on-Cand-Param Info Type
Make Assumptions on Candidate Parameters Knowledge
Determine Parameters Suitable for Extension
Det-Param-Suit-for-Exten Info Type
Determine Parameters Suitable for Extension Knowledge

Table 3: Internal information type and knowledge base for subtasks of 'Extension Suitability Determination'

Information types can be defined in a compositional manner by combining them from sub information types. This can be specified by means of a relation defining a tree as is shown in Table 4.

information type

sub information type
Det-Non-Cand-Param Info Type
Parameter Dependencies Info Type
Det-Non-Cand-Param Info Type
Parameters in Current RQS Info Type

Table 4: Hierarchy of information types.

Graphical representations can be made in tree or block form. The same can be done for knowledge bases, as is shown in Table 5.

knowledge base

sub knowledge base
Determine Non-Candidate Parameters Knowledge
Parameters in Current RQS Knowledge
Determine Non-Candidate Parameters Knowledge
Parameter Dependency Knowledge

Table 5: Hierarchy of knowledge bases

2.6 Detailed specification

Specification of a system is most often an iterative process: in time more detailed knowledge is acquired and modelled. The types of knowledge described during conceptual analysis have a (unique) counterpart in the specification. The types of knowledge become more explicit, and are defined more precisely.

Each task is mapped onto a component. Each component has a uniform structure (see Figure 5), that distinguishes between task control information and kernel information. The kernel information of a primitive (monotonic) component corresponds to a knowledge base, whereas the kernel of a composed (possibly non-monotonic) component consists of subcomponents and information links. The task control information of a primitive component consists of an inference engine, whereas the task control of a composed component consists of knowledge about task control. Another distinction made in the uniform structure is between public and private information, which fulfills the notion of information hiding.

Figure 5: Uniform structure of a component.

During detailed specification (primitive) tasks are mapped onto (primitive) components, information exchange onto information links, and task sequencing knowledge onto task control knowledge. Moreover, the input, output and internal information types need to be mapped upon signatures (in our case: sets of ground atoms). This entails:

The detailed specification is reflected in the syntax of DESIRE. Closely related to syntax is the formal semantics that gives it formal meaning. A state-based semantics is chosen where each component has an information state. Partial models (Blamey, 1986; Langholm, 1988) are used to formalise information states, representing (incomplete) world descriptions (e.g., Langen and Treur, 1989). To define formal semantics of reasoning behaviour in (hierarchical) compositional architectures, a recently developed approach based on (partial) temporal models is adopted (Engelfriet and Treur, 1994; Gavrila and Treur, 1994; Treur, 1994). Within this approach the semantics of a complex reasoning process is formalised by a set of (alternative) reasoning traces. A reasoning trace is formalised by a partial temporal model, i.e., a sequence of partial models. The next section elaborates on the temporal semantics of reasoning behaviour.

2.7 Comparison to other approaches

The formal specification framework DESIRE has been compared to other approaches. The formal specification language of DESIRE has been shown to be more flexible in modelling reasoning patterns (Harmelen and Fensel, 1995). In terms of expressive power, declarativeness, adequacy to specify dynamic aspects of reasoning patterns, possibility to specify multi-level architectures, adequacy to specify non-classical reasoning, executability and availability of formal semantics, the formal specification language within the DESIRE framework is to some extent comparable to other formal specification languages such as (ML)2 (Akkermans, Harmelen, Schreiber, and Wielinga, 1992) and KARL (Fensel, 1993). It differs in that it is executable and can specify integrated systems. The formal specification languages languages differ in expressiveness of control knowledge (Treur and Wetter, 1993; Fensel and Harmelen, 1994).

Task control knowledge within DESIRE is located within each composed task (or component); i.e. distributed control. In (ML)2 and KARL task control knowledge is expressed in a separate layer. Also the ability to perform reflective reasoning (both upward and downward reflection) is a major difference, enhancing DESIRE's flexibility in modelling reasoning patterns.


Behaviour is formalised as sequences of information states in which truth-values are assigned to elements describing the domain a component is reasoning about. The current state of a system is reflected by the current assignment of truth-values. The behaviour of a compositional architecture is mirrored in its successive (overall) information states, each defined by the composition of the information states of its sub-components.

The elements used to describe the states (the ground atoms) are expressed in a language that is defined by a signature. Each component within a compositional architecture has an information state describing the truth values (false (0), true (1) and undefined (u)) of atoms of the component.

Definition 3.1 (signature, information state) A signature is a structure of symbols defining a set of ground atoms At(). An information state for a signature is a mapping from the set of ground atoms At() to the set of truth values {0, 1, u}; i.e. a (partial) model M : At() {0, 1, u}. The set of all information states of signature is denoted by IS().

An example of a structure defining a signature is a tuple of (sub)sorts, constants, functions, and predicates of a many-sorted predicate logic, used in the DESIRE specification below, as is the use of referenced signatures for importing already defined signatures.
signature RequirementParameter_sig
end signature

signature NonCandidateReqParm_sig
  referenced signatures
    non-candidate: RequirementParameter;
end signature

The set of ground atoms defined for NonCandidateReqParm_sig is defined as follows:

< non-candidate(car_cab_height), ..., non-candidate(car_phone), ..., non-candidate(platform_width) >

Formalising information states as partial models is sufficient to model the reasoning behaviour of common inference mechanisms, such as chaining or unit-resolution, in terms of all ground literal conclusions that have been derived up to a certain moment in time.

Behaviour is the result of transitions from one information state to another. Transitions are defined within the compositional structure of the information states they manipulate: a transition only changes the information state in one of its components.

Definition 3.2 (transition) A transition between information states is a pair of partial models; i.e., an element {S, S'} (also denoted by SS') of IS([Sigma]) x IS([Sigma]). A transition relation is a set of these transitions, i.e. a relation on IS() x IS().

If a transition relation is functional then it specifies deterministic behaviour. By applying transitions in succession, sequences of states are constructed. These sequences, also called traces (and interpreted as temporal models), formally describe behaviour. They adhere to the compositional structure: a trace describes a composed information state that develops in time (see Figure 6).

Definition 3.3 (trace and temporal model) A trace or partial temporal model of signature is a sequence of information states (Mt)t N in IS(). The set of all partial temporal models is denoted by IS()N, or Traces().

A set of partial temporal models is a declarative description of the semantics of the behaviour of the system; each temporal model can be seen as one of the alternatives for the intended behaviour.

Figure 6: Information states in time.


To describe composed tasks (tasks composed of subtasks) information states need to reflect the compositional structure. Below component refers to both composed and primitive components, unless explicitly specified. The information state of a component changes as a result of (1) input received from other components (public information) or (2) the execution of the corresponding task.

The execution of the corresponding task changes both the internal information state of the component (private information) and the output information made available to other components (public information). The private information is based on internal signatures and signatures of the public input and output; during execution inputs are taken from the input interface (input buffer) and outputs are transferred to the output interface (output buffer). The distinction between public and private information within a component is shown in Figure 5. Also the distinction between task (control) related information and kernel related information is shown in Figure 5.

Definition 4.1 (public kernel information) Each component C is assigned a signature, called the public kernel signature of C, denoted by C,pubker. The input and output parts are subsignatures, denoted by C,inker and C,outker. The public kernel information state for C is the information state for signature C,pubker and the fixed set of public kernel information states for C is denoted by ISpubker(C).

Kernel information states can be either primitive or composed. The atoms which determine a primitive kernel information state are defined within the kernel of a primitive component (e.g., the signature of a knowledge base). The kernel information state of a composed component is a combination of the kernel information states for the component's subcomponents.

Definition 4.2 (kernel information state) Let D be a component.
a) If D is primitive, then its set of private kernel information states is defined by:

ISpriker(D) = IS(D,priker)
Here D,priker is the overall private signature assigned to D: contains both internal elements and copies of signatures of public (input and output) interface.
b) If D is composed and its set of children components is denoted by Ch(D), the set of private kernel information states for D is recursively defined by:
ISpriker(D) = C Ch(D) ISker(C)
c) For any component D the set of kernel information states is the combination of public and private information states
ISker(D) = ISpriker(D) x ISpubker(D)
In this combination there is still a distinction between public information states (see definition 4.1) and private information states. This formalises how the interface serves as a buffer between the private kernel and other components.

An example of a composed information state is shown in Figure 9, where each of the columns is a composed information state.

The private part of the information state of the task control component can be constructed in a similar manner. The task control knowledge is used to supervise the activations of the kernel (both subcomponents and information links). Task control information includes specification of sets of goals and requests, exhaustiveness of search, etc: the additional information required to execute a task.

Definition 4.3 (task control information state) The task control of a component C is modelled as a component. Similar to definitions 4.1 and 4.2 an information state is defined.

a) For any component D the set of public task control information states is defined by:

ISpubtc(D) = IS(D,pubtc)
that in turn is split into input and output information state.
b) For any component D the set of private task control information states is defined by:
ISpritc(D) = IS(D,pritc)
c) For any information link I the set of (public) task control information states is denoted by:
d) The task control information state of a primitive component C is defined as
IStc(C) = ISpubtc(C) x ISpritc(C)
e) If a component D is composed, the set of composed task control information states of the component D is defined as the composition of all task control information of children components C and kernel links I of D (formally defined in Section 5.1):<
IScom,tc(D) = C C(D) IStc(C) x I KL(D) IStc(I)
f) The task control information state of a composed component D is defined as
IStc(D) = ISpubtc(D) x ISpritc(D) x IScom,tc(D)
The definitions d) and f) combine all parts of a component that contain control information and at the same time distinguish the interface (public) control information from private control and possibly the control of each subcomponent.

The knowledge about the private task control is specified explicitly in DESIRE; the signatures used are generic (including relations such as next-state, next-uptodate-link, ...), see Section 5.2.

The kernel and the task control together define the information state of components.

Definition 4.4 (component information states) Let D be any component.

The set of information states of D is defined as:

IS(D) = ISker(D) x IStc(D)
This definition reflects the distinction between kernel and control information that is available in every component.

Another distinction in the structure of the information state can be made. The kernel input and output interface are not merely a collection of signatures, but are viewed as a combination of signatures, where signatures are grouped in levels, and levels are ordered in an object/meta/meta-meta/...-relation.

In the context of compositional structures and for the specification of detailed process information the notion of levelled signatures is important. The specification of more detailed dynamics is modelled through (meta-level) reasoning of one level about the state of the process of the level below.


The notion of a transition relation can be generalised for the compositional case, defining a compositional transition relation. A binary relation is defined between a tuple of information states (left hand side, precondition of the transition) and another tuple of information states (right hand side, result of the transition). This transition relation between one part of a compositional state and another part of a compositional state induces a transition relation for the compositional state as a whole.

Transition relations exist both within and between components. An information state of a component can be changed either because a component has been active and generated new information itself, or because information has been transferred/exchanged from one component to another. Transitions between components are specified by information links as defined below. Transitions within components are either transitions within the kernel, transitions within the task control, or transitions between task control and the kernel.

5.1 Transitions between components

To enable information exchange between components, information links are specified: between two components (private links) or between (the interface of) a component and one of its subcomponents (a mediating link), as shown in Figure 7.

Figure 7: Kernel information links.

Information links are the logical basis for information exchange between components. It is assumed that the interface of every component consists of one or more (meta-)levels as explained above. Activations of a link from component C1 to component C2 causes a change in the information state of C2 on the basis of information available in C1. This change is a refinement or (for updates) a non-conservative modification of the information state of C2. In effect it implies an extension, update or revision of the information state. A (relative) principle of conservation is assumed: all information that is not explicitly changed by an activation of a link will remain available (a specific frame assumption). The task control component controls the activation of the various links.

An information link is defined on the basis of semantic units: atoms and their truth values. In principle it relates a semantic unit of a component C1, defined by a pair < a, tv1 > of a ground atom a of one signature and a truth value tv1 to a semantic unit of another component C2, defined by a pair < b, tv2> with b of another signature. Atoms which refer to the same entities in the world may be named differently within different components, in which case an information link defines the "translation" of atom names.

Definition 5.1 (semantic unit, kernel information link)

Let D be a complex component and C, C1 and C2 its subcomponents. The set of public semantic units of level x for the kernel of a component C is defined by

SU(x)(C) = At(C,pubker,(x)) x {0, 1, u}
SU(x)in(C) resp. SU(x)out(C) denotes the restriction of this set to inputs resp. outputs.

a) A private kernel link of D, I from level x of C1 to level y of C2 is a binary relation

I : SU(x)out(C1) x SU(y)in(C2)
b) Likewise, the mediating kernel links are defined as
I : SU(x)in(D) x SU(y)in(C)
I : SU(x)out(C) x SU(y)out(D) and
I : SU(x)in(D) x SU(y)out(D)

A trivial standard example of an information link is when the sets of semantic units have a common subset U, and for < a, tv1 > SU(x)out(C1), < b, tv2 > SU(y)in(C2) the identity relation I is defined by I(< a, tv1 >, < b, tv2 >) if < a, tv1 > = < b, tv2 > U. Note that by restricting this subset U restricted information exchange is specified.

In the example below, the name of the parameter to be deduced is passed to the component that deduces an additional value. The transfer specified by a mediating link translates poss_ass( likely_candidate( X: RequirementParameter ) ) to candidate( X: RequirementParameter ).

  private link pass_to_deduce_reqparm: object-assumption
    domain make_assumption_on_candidate_parameter
      output output_1
    co-domain determine_parameter_suitable_for_extension
      input input_2
    sort links
      (RequirementParameter, RequirementParameter)
      (Value, Value )
    object links identity
    term links identity

atom links

(poss_ass( likely_candidate(P: RequirementParameter)), assumption(candidate( P: RequirementParameter), positive)): <<true, true>, <false, false>, <unknown. false> >; end link

The dynamic semantics of such information links can be expressed by the notion of transition introduced in Section 3. Note that a simple transition between one or more factors of a cartesian product can be extended in a canonical manner to a relation on the whole cartesian product. Thus
: (A x B)x(B x C) with (< a, b >, < b', c' >)
induces the relation * : (A x B x C )x(A x B x C)

that is *(< a, b, c >, < a', b', c' >) with a' = a
whenever (< a, b >, < b', c' >)
Factors that are not influenced by the transition can be added on the left hand side or left unchanged in the transition (conservation).

Definition 5.2 (information link transition) Suppose E1 and E2 are components and I is a information link from level x of E1 to level y of E2.
A transition relation for the information link I is a relation

: (ISx(E1)xISy(E2) x IStc(I)) x (ISy(E2)xIStc(I))
such that for all M1, M2, N, M'2, N' with (< M1, M2 , N >, < M'2, N' >)
and for any atom b
M'2(b) = M2(b) (conserved) or
I(< a, M1(a) >, < b, M'2(b)>) for some atom a (changed by the link)

5.2. Transitions due to task control

Task control is specified explicitly in DESIRE; the signatures used are generic. In the example below the task control of the component extension suitability determination is specified: this task can be activated to determine a parameter (indicated by the target-set in the condition), terminating when a default value has been determined.
  task control extension_suitability_determination
    task control knowledge
      if start
        and target-set( determine_suitable_parameter)
        then next-state( determine_non_candidate_parameter, active)
        and next-target-set( determine_non_candidate_parameter, determine)
        and next-uptodate-link( a1 );
      if evaluation( determine_parameter_suitable_for_extension, det_suit_param, succeeded, any )
        then stop
        and next-uptodate-link( pass_suitable_parameters_to_output );
  end task control

Definition 5.3 (task control transition) A task control transition relation for a component C is a relation associating task control information states for C to task control information states for C; i.e., a relation : IStc(C) x IStc(C) where each transition is induced by the task control specification.

The task control information must, in some way, be transferred between the task control of the parent component and the task control information of the subcomponents. Three kinds of task control links are discerned: upward task control links, and downward task control links that connect the private task control to the subcomponent and sublink task control, and thirdly the mediating task control links that communicate the private task control to the public task control and vice versa (see Figure 8).

Figure 8: Task control links

Formally, task control links are defined as follows. For example, each component C has a downward link defined by the pair < next-state(C, active), 1 >, < state(active), 1 >.

Definition 5.4 (task control link) Let D be a composed component and let the set of semantic units SUpritc be defined by SUpritc(D) = At(D,pritc) x {0, 1, u}.

a) A (combined) downward task control link (denoted by DTCL) is a set consisting, for each subcomponent C, of a relation on

I : SUpritc(D) x SUintc(C)
where SUintc is defined by SUintc(C) = At(C,pubtc) x {0, 1, u}
b) A (combined) upward task control link (denoted by UTCL) is a set consisting, for each subcomponent C, of a relation on
I : SUouttc(C) x SUpritc(D)
where SUouttc is defined by SUouttc(C) = At(C,pubtc) x {0, 1, u}
c) A (combined)mediating task control link (denoted by MTCL) are relations
I : SUintc(D) x SUpritc(D) or I : SUpritc(D) x SUouttc(D)
Note that in the specification language DESIRE these task control links are left implicit. Unlike for kernel links, it is not necessary to specify these control links.

Definition 5.5 (task control link transition) Let D be a complex component.

a) A transition relation for the upward task control link UTCL is defined as a relation

UTCL : (IScom,tc(D) x IStc(D)) x IStc(D)
such that for all N1, N2, N'2 in UTCL (<N1, N2>, N'2) it holds that for any atom b :
N'2(b) = N2(b) (conserved) or
I(< a, N1(a) >, < b, N'2(b)>) for some atom a (changed by a link).
b) A transition relation for the downward task control link DTCL is defined as a relation
DTCL : (IStc(D) x IScom,tc(D)) x IScom,tc(D)
such that for all N1, N2, N'2 in DTCL ( <N1, N2>, N'2) it holds that for any atom b :
N'2(b) = N2(b) (conserved) or
I(< a, N1(a) >, < b, N'2(b)>) for some atom a (changed by a link).

5.3. Compositional Transitions

For primitive reasoning components, kernel transitions are induced by inferences on the basis of knowledge in the knowledge base. Compositional transitions define the dynamic semantics of hierarchical compositional systems.

Definition 5.6 (kernel transitions) Let C be a component. A kernel transition relation for a component C (or private component transition relation) is a relation associating information states for C to information states for C; i.e., a relation

: ISker(C) x ISker(C)
where each transition is induced by either a kernel transition relation of a (child) component or by a transition of an information link.

Definition 5.7 (compositional transitions) Let D be a composed component with subcomponent C. A compositional transition relation for the D is a transition relation

: ISpri(D) x ISpri(D)
where each transition is induced by a transition of one of the following types:

(1) a kernel transition, (2) a task control link transition, (3) a task control transition.
In Figure 9 the three subtypes of compositional transitions are shown. The information states are changed according to the specifications given of kernel contents (above), task control contents (Section 5.2), and the implicit task control links.

The following definition shows how traces generated by iteratively applying a transition function on the current information state can be interpreted as temporal models giving a declarative description of the semantics of the behaviour of the system; they can be viewed as the intended (behavioural) models of the system.

Figure 9: A trace of information states.

Definition 5.8 (compositional trace) Let D be a component.

a) A trace of a component D is a sequence of information states (Mt)t N in IScom(D). The set of all traces is denoted by IS(D)N, or Traces(D).

b) An element (Mt)t N Traces(D) is called a temporal model of D if for all time points t the step from Mt to Mt+1 is defined in accordance with a compositional transition of the system. The set of temporal models of D forms a subset BehMod(D) of Traces(D).

A temporal model describes a trace representing possible (intended) behaviour of the reasoning. One view is that the trace is generated by the (execution of) transition functions, given initial input information. From every initial information setting a trace can be generated by the transitions. Together the generated traces form the set BehMod(D). A slightly different view is that the transition relations define a set of (temporal) axioms or constraints BehTheory(D) on temporal models in Traces(D). The possible behavioural alternatives are given by the set of the temporal models satisfying these temporal constraints:

TempMod(D) = { M Traces(D) | M BehTheory(D) }
where M BehTheory(D) holds iff each formula from the set BehTheory(D) has truth value true at every time point in the temporal model M. This second view provides a formalisation of the intended behavioural patterns in the form of the (intended) models of a logical (temporal) theory in a specific type of temporal logic, giving a declarative (Tarski) semantics. The formal semantics of the behaviour is defined by the set of models TempMod(D). The first view corresponds to the notion of an executable temporal logic. Both views co-exist: executing a temporal theory is a useful technique to construct a model of this theory.


The formal approach to modelling and specifying complex dynamic tasks introduced in this paper is based on the assumption that dynamic aspects are essential for modelling complex tasks. A compositional framework has been presented within which a language for the specification of compositional architectures has been introduced together with the semantics of such architectures for complex dynamic tasks. The temporal approach to the description of a compositional system's behaviour presented provides a means to describe the dynamics involved. Temporal logic is used to formalise the semantics. The state of a composed component, at any given point in time, is described as a set of the states of the composed component's subcomponents and the state of the task control. The compositional structure of information states, transitions and reasoning traces provides a transparant model of the system's behaviour, both conceptually and formally. Such a model of a system's behaviour serves as the basis for temporal reasoning on the control of the behaviour of the system.

Another formal specification language that supports hierarchical task structures is KARL (Fensel, 1993) in which inference actions can be defined in terms of other (more primitive) inference actions. This language is related to the KADS methodology (Schreiber, Wielinga, and Breuker, 1993) with its three independent (hierarchically organised) layers. In KADS, hierarchical decomposition is only available at the task layer. The introduction of hierarchical decomposition at the inference layer in KARL is an extension of KADS. In KARL the decomposition of the inference layer is in a one to one correspondence to the decomposition of the task layer. Similar to the approach here the semantics attributed to a composed inference action takes into account the related control structure at the task layer and the primitive inference actions included. A difference with our approach is that in our specification this related control structure is included in the composed component itself and not separated at a distinct (task) layer. This implies that in our case the specification document mirrors the compositional structure more explicitly, in the sense of 'hiding' the control inside the composed component. Moreover, in KARL the temporal aspects are not explicitly covered by the formal semantics that assigns a 'static' (input-output) semantics to the inference layer independently from the task layer. A conclusion from our work presented here is that control and temporal semantics are necessarily intertwined for models of complex (non-monotonic) tasks.

In particular, for applications in which the interaction between components that reason and act autonomously, such as cooperative (human-computer) systems and multi-agent systems, the dynamics of interactions is crucial. These interactions take place in a dynamically controlled manner and can be modelled in our temporal framework by transitions between states. As KADS is based on a different conceptual model (the four layer model), in which the notions of state and transition are left implicit, KADS languages like KARL and (ML)2 have difficulty expressing dynamically controlled interactions between autonomous components in an adequate manner.

A formal basis to the conceptual phase of complex system design, supporting knowledge acquisition and within which behaviour can be explicitly modelled, is available. Reuse of formally specified (sub)components of a system is possible. The behaviour of the (sub)components in interaction with other (sub)components can be well-defined. In current research multi-agent situations, in which agents are modelled as interacting components, are being explored. Given compositional descriptions of complex dynamic systems, together with well-defined semantics, validation and verification of system behaviour should be possible. Initial research in this area is promising (Treur and Willems, 1995). Within the context of the approach described, further foundational research with respect to modelling complex reasoning can be investigated: more intricate patterns of reasoning behaviour can be explored and formally described.


This research was partly funded by the Netherlands Organization for Scientific Research (NWO) within the REVISE project "Evolutionary design in knowledge-based systems" (project number 612-322-316) and the ESPRIT III Basic Research project 6156 DRUMS II.


Agusti, J., Esteva, F., Carcia, P., Godo, L., Lopez de Mantaras, R., Murgui, Ll., Puyol, J., and Sierra, C. (1992). Structured Local Fuzzy Logics in MILORD, In: Zadeh, L., and Kacprzyk, J. (Eds.) Fuzzy Logic for the Management of Uncertainty, John Wiley & Sons, Inc.

Akkermans, J.M., Harmelen, F. van, Schreiber, A.Th., and Wielinga, B.J. (1992). A formalisation of knowledge-level models for knowledge acquisition. Int. J. Of Intelligent Systems.

Blamey, S. (1986). Partial Logic. In: D. Gabbay and F. Günthner (Eds.), Handbook of Philosophical Logic. Vol. III, pp. 1-70, Reidel, Dordrecht.

Brazier, F.M.T., Dunin-Keplicz, B., Jennings, N., and Treur, J. (1995). Formal Specification of Multi-Agent Systems: a Real-World Case, Proceedings First International Conference on Multi-Agent Systems, ICMAS'95, pp. 25-32.

Brazier, F.M.T., Langen, P.H.G. van, Ruttkay, Zs. and Treur, J. (1994). On the formalisation of design processes. In: Gero, J.S. (Ed.), AI in Design, Proceedings AID'94, Kluwer Academic Publishers, Dordrecht, pp. 535-552.

Brazier, F.M.T., Langen, P.H.G. van, Treur, J., Wijngaards, N.J.E. and Willems, M. (1996). DESIRE: Designing an elevator configuration. In: Schreiber, A.Th., and Birmingham, W.P. (Eds.), Special Issue on Sisyphus-VT. International Journal of Human-Computer Studies, 1996, Volume 44, pp. 469-520.

Brazier, F.M.T., and Treur, J. (1994). User centered knowledge-based system design: a formal modelling approach. In: Steels, L., Schreiber G. and Velde, W. van de (Eds.), A Future for Knowledge Acquisition, EKAW'94, Proceedings, Springer-Verlag, Dordrecht, pp. 283-302.

Brazier, F.M.T., Treur, J. and Wijngaards, N.J.E. (1996). The acquisition of a shared task model. In: Shadbolt, N., O'Hara, K., and Schreiber, A.Th. (Eds.). Advances in Knowledge Acquisition; 9th European Knowledge Acquisition Workshop, EKAW'96, Lecture Notes in Artificial Intelligence, Volume 1076, Springer Verlag, pp. 278-289.

Brazier, F.M.T., Treur, J., Wijngaards, N.J.E., and Willems, M. (1995). Formal specification of hierarchically (de)composed tasks. In Gaines, B.R. and Musen, M.A. (Eds.), Proceedings of the 9th Banff Knowledge Acquisition for Knowledge-Based Systems Workshop, KAW '95, Volume 2, pp. 25/1-25/20. Calgary: SRDG Publications, Department of Computer Science, University of Calgary.

Engelfriet, J. and Treur, J. (1994). Temporal theories of reasoning. In: MacNish, C., Pearce, D., and Pereira, L.M. (Eds.), Logics in Artificial Intelligence, Proceedings of the 4th European Workshop on Logics in Artificial Inteligence, JELIA'94, Springer-Verlag, volume 838 of Lecture Notes in Artificial Intelligence, pages 279-299.

Fensel, D. (1993) The knowledge acquisition and representation language KARL, PhD. Thesis, Univ. of Karlsruhe.

Fensel, D., Harmelen, F. van, (1994) A comparison of languages which operationalize and formalize KADS models of expertise. Knowledge Engineering Review, Volume 9, pp. 105-146.

Gavrila, I.S. and Treur, J. (1994). A formal model for the dynamics of compositional reasoning systems, in Cohn, A.G. (Ed.), Proc. 11th European Conference on Artificial Intelligence, ECAI'94 , John Wiley & Sons, Chichester, pp. 307-311.

Geelen, P.A., and Kowalczyk, W. (1992) A knowledge-based system for ruting of international blanc payment orders, In: Proc. of Int. Conf. on AI, Expert Systems and Natural Language, Avignon-92, vol 2, pp. 669-677.

Harmelen, F. van, and Fensel, D. (1995). Formal methods in knowledge engineering. The Knowledge Engineering Review, Volume 10(4), pp. 345-360.

Langevelde, I.A. van, Philipsen, A.W. and Treur, J. (1992). Formal specification of compositional architectures. In: Neumann, B. (Ed.), Proc. 10th European Conference on Artificial Intelligence, ECAI'92, John Wiley & Sons, Chichester, pp. 272-276. Extended version: Report IR-282, Vrije Universiteit Amsterdam, Department of Mathematics and Computer Science, 1991

Langen, P.H.G. van, and Treur, J. (1989). Representing World Situations and Information States by Many-Sorted Partial Models. Technical Report PE8904, University of Amsterdam, Department of Mathematics and Computer Science.

Langholm, T. (1988). Partiality, Truth and Persistence. CSLI Lecture Notes, No. 15. Stanford University, Stanford.

Schreiber, A.Th., Wielinga, B.J. and Breuker, J.A. (Eds.) (1993). KADS: A Principled Approach to Knowledge-Based System Development. Academic Press, London.

Treur, J. (1994), Temporal Semantics of Meta-level Architectures for the Control of Reasoning, In: Turini, F. (Ed.), Lecture Notes in Comp. Sc. 883, Springer-Verlag.

Treur, J. and Wetter, Th. (Eds.) (1993). Formal Specification of Complex Reasoning Systems, Ellis Horwood.

Treur, J. and Willlems M (1995). On verification in compositional knowledge-based systems. In: Rousset, M.-C. and Ayel, M. (Eds.), Proceedings European Symposium on Validation and Verfication on KBSes, EUROVAV'95, Chambéry.