next up previous
Next: SOLVABILITY OF SEPARABLE DCPS Up: ENVIRONMENTSPOLICIES, AND REDUCIBILITY Previous: ENVIRONMENTSPOLICIES, AND REDUCIBILITY

 

PRODUCT ENVIRONMENTS

The majority of the formal sections of this paper will explore the phenomenon of factoring. In particular, we will explore how policies for factorable environments can be composed from policies for the factors. In state-machine models of environments, factorization is the factorization of the state-space; the environment's state-space is a Cartesian product of other state-spaces. The environment, as a whole, is ``factorable'' into its component sub-environments. For example, the position of the king on a chess board has row and column components. It can be thought of as the ``product'' of those components, each if which is isomorphic to tex2html_wrap_inline1672 (since there are eight rows and eight columns). If we consider an environment in which a car drives through an tex2html_wrap_inline1674 grid of city blocks, we see that it too is a kind of product of tex2html_wrap_inline1672 with itself. Both environments have tex2html_wrap_inline1674 grids as state spaces, but the car environment only allows one component to change at a time, whereas the king environment allows both to change.

We must therefore distinguish different kinds of factorization. We will call the chessboard case the parallel product of tex2html_wrap_inline1672 with itself, while the car case is its serial product.    We will focus on another kind of factorization later. Let the Cartesian product of two functions f and g be tex2html_wrap_inline1686 , and let i be the identity function. For two environments tex2html_wrap_inline1690 and tex2html_wrap_inline1692 , we will define the parallel product to be

displaymath1664

and the serial product to be

displaymath1665

The products of DCPs are defined in the obvious way:

displaymath1666

displaymath1667

The state diagram for tex2html_wrap_inline1694 is shown in Figure 1.

We will say that an environment or DCP is parallel (or serial) separable if it is isomorphic to a product of environments or DCPs.




next up previous
Next: SOLVABILITY OF SEPARABLE DCPS Up: ENVIRONMENTSPOLICIES, AND REDUCIBILITY Previous: ENVIRONMENTSPOLICIES, AND REDUCIBILITY

Ian Horswill
Wed Apr 2 15:17:20 CST 1997