Processes

Processes can be described by their starting and stopping points and by the kinds of changes that take place in between. Figure 1 shows the category Process subdivided by the distinction of continuous change versus discrete change. In a continuous process, which is the normal kind of physical process, incremental changes take place continuously. In a discrete process, which is typical of computer programs or idealized approximations to physical processes, changes occur in discrete steps called events, which are interleaved with periods of inactivity called states. A continuous process with an explicit starting point is called an initiation; one with an ending point is a cessation; and one whose endpoints are not being considered is a continuation.

Figure 1: Types of Processes

Beneath each of the five categories at the leaves of Figure 1 is an icon that illustrates the kind of change: a vertical bar indicates an endpoint, a wavy horizontal line indicates change, and a straight horizontal line indicates no change. A discrete process is a sequence of states and events that may be symbolized by a chain of straight and wavy lines separated by vertical bars. A continuous process may be symbolized by a continuous wavy line with occasional vertical bars. Those bars do not indicate a break in the physical process, but a discontinuity in the way the process is classified or described. The weather, for example, varies by continuous gradations, but different time periods may be classified as hot or cold, cloudy or sunny.

The categories in Figure 1 could be further differentiated according to the kinds of participants that are involved in the process and how they interact with one another. An action is an event caused by an agent, and an activity is an extended process (continuous or discrete) caused by one or more agents over some time interval. The agent's intentions may also be important for determining the classification: a cessation that satisfies an agent's goals is considered a success, and one that does not satisfy the goals is a failure. For more detail, see the web pages on causality, agents, roles and relations, and thematic roles. The fundamental principles and techniques for doing the classification are discussed in the book Knowledge Representation.

In natural languages, the features of tense and aspect relate the event described by a verb to the type of process and to the reference times of one or more observers. The simple tenses -- past, present, and future -- relate the time of an event to the time of the speech. The compound tenses, such as past perfect or future perfect, involve an additional reference time in some real or hypothetical past or future. Aspect describes the initiation, continuation, or completion of some action with respect to the reference times. Whether an action is continuing or completed may depend on some agent's intentions. The definitions of many verbs depend on the intentions of their agents, and the same physical process described by different verbs can be classified in very different ways. Different classifications, in turn, have different implications. Depending on the verb that is used to describe an action, the agent may be praised for a success or blamed for a failure.

In his book Features and Fluents, Erik Sandewall presented a detailed taxonomy of process types, their representation in logic, and the techniques for reasoning about them. His taxonomy is determined by a list of distinctions based on the complexity of the interactions and the kinds of representations needed to describe them:

• Discrete or continuous. In physics, continuous processes are represented by differential equations. On digital computers, time is divided into discrete time points, which may be called integer time when they are numbered 0, 1, 2.... Continuous processes can be approximated by decreasing the time step of a discrete process and thereby increasing the number of points that must be represented, stored, and computed. Differential equations represent the limiting case when the time step approaches zero and the number of points approaches infinity.

• Linear or branching. A linear order of time points and their associated events creates a deterministic process that is easy to represent and compute. Conditional alternatives, however, create branching time, with a nondeterministic increase in the future possibilities that must be represented and analyzed.

• Independent or ramified. If the variables that describe a process are independent, a change to one has no effect on the others. In a ramified process, a change in one variable can cause changes in the others. Sandewall drew a three-way distinction: local independence, where all the variables are independent; local ramification, where an event that changes one variable only changes other variables that are directly involved in the same event; and structural ramification, where the effects of changing one variable may propagate to other events and cause indirect changes to remotely related events.

• Immediate or delayed. If the changes caused by an event occur immediately, they can be represented or simulated during the same time step as the event. A delayed effect, however, does not cause an observable change until some subsequent states or events.

• Sequential or concurrent. In a sequential process, only one event occurs at any instant. In a concurrent process, multiple independent events may occur in parallel.

• Predictable or surprising. A predictable process follows a script that specifies all the possible causes and effects of each event. A surprising or exogenous event causes a change that is not anticipated by the script.

• Normal or equinormal. Some processes have a highly probable or normal flow of events that can be assumed as the default. In an equinormal process, multiple courses of events are equally likely, and no single outcome can be considered the default.

• Flat or hierarchical. In a flat process, each event is described by a short list of the changes it can cause. In a hierarchical process, any event may be composed of subevents. A third option is a recursively hierarchical process, in which some events are composed of subevents of the same type.

• Timeless or time-bound. The simplest processes to analyze involve a fixed number of timeless objects that are neither created nor destroyed during the process. Time-bound objects, which may be created or destroyed during the interval of interest, lead to processes with an ever-changing inventory of objects.

• Forgetful or memory-bound. In a forgetful process, the future course of events depends only on the current state, not on the history of how the current state came about. A memory-bound process retains some information from earlier states, which may affect future outcomes.

The icons shown in Figure 1 can be linked end to end in a timing diagram to represent a history of the process. At the bottom of Figure 2 is a timing diagram for a clock, which is a discrete, linear, independent, immediate, sequential, predictable, normal, flat, timeless, forgetful process. The history of the clock process shows an open-ended sequence of states separated by negligibly short events called ticks. Each tick causes an integer, called a counter, to be incremented by one.

Figure 2: Concurrent processes timed with a clock

Above the timing diagram for the clock is a timing diagram for a concurrent process, which has varying numbers of subprocesses, called threads, that run in parallel. The events and states of the process can be timed by comparing their occurrences with the numbered ticks of the clock process. The concurrent process shown in Figure 2 represents a history of firings of a Petri net, which is discussed in Chapter 4 of the book Knowledge Representation. For further discussion of Petri nets and their use in representing processes, see the web page on causality.

Sandewall's list does not exhaust all the possible distinctions for classifying processes. A system designer, for example, might distinguish a process local to a single system from a process distributed across a network. Sandewall did not consider that distinction because the location of a process is independent of the methods for reasoning about it. For different purposes, new categories can be generated by adding more distinctions to the list or by deleting some that are not relevant.

For further discussion about continuous processes, discrete processes, and causal influences, see the paper on Processes and Causality.

Send comments to John F. Sowa.

  Last Modified: