1 SYNTHESIS IN COMPLEX PROBLEM DOMAINS INFORMATICA 4/89 Keywords: synthesis, complex systems, abstraction, hierarchical decomposition, structuring Maksimilijan Gerkeš Metalna Maribor ABSTRACT: Complex systems' synthesis becomes a bottleneck of production process. Some researchers denote this situation as crisis, others as "crisis". However, complex systems' synthesis especially those, which cannot be implemented within particular technology domain is an open problem. The contribution gives a collection of procedures, developed with integration and some ¡novations of classical procedures and more advanced procedures. As a result, synthesis process can be based on abstraction, hierarchical decomposition, and structuring, while its derivation is nested in actual technological context, expressed through requests synthesized solution must satisfy. POVZETEK: Sinteza v domeni kompleksnih problemov Sinteza kompleksnih sistemov postaja vedno bolj ozko grlo produkcijskega procesa. Nekateri raziskovalci označujejo to stanje kot krizno, drugi kot "krizno". Kakorkoli, problem sinteze kompleksnih sistemov, posebej tistih, ki jih ni možno rešiti v domeni posamezne tehnologije, je dokaj odprt. Prispevek podaja skupek postopkov izpeljanih, z integracijo in nekaj inovacijami, iz klasičnih postopkov in sodobnih postopkov sinteze. Kot rezultat lahko postopek sinteze gradimo na osnovi abstrakcije, hierarhične dekompozicije in strukturiranja, njegovo izvajanje pa je vgnezdeno v konkretni tehnološki kontekst izražen v obliki zahtev, ki jih mora izpolnjevati rešitev. INTRODUCTION synthesis tools to be developed for each particular technology. Even if this is possible, there will still Situation in high technology domains like CIM, flexible manufacturing, software, computer architectu-tes, VLSI, etc., seems similar regarding the requests for more efficient synthesis methods. For economic reasons synthesized solutions must be completely validated before manufacturing. A single error can cause exponential growth of operations to dispatch it. This calls for formal correct synthesis methods. complexity and functionality issues of contemporary and advanced systems. remain the problem of systems implemented in diverse technologies. This clearly calls for synthesis methods, which will be technology independent and conceptualized on This contribution is based on system orientation to the synthesis problem, where current technology Complexity is common characteristic of systems in the above domains. It causes an enormous amount of operations, before the synthesis goal can be satisfied. Most of the contemporary synthesis methods seem to fail because of their too close technological orientation. exact limits during the synthesis process, technological objectives are not expressed explicitly, but reflect in sets limits regarding system's functionality and structure. Such an approach allows that technology based descriptions are completely avoided until the solution representation level. Altough technology sets very Rapid technology development disables efficient system structure and functionality. An approach to synthesis is used, which is based on abstract system representation transformed through hierarchical decomposition and structuring to its counterpart, the solution. Abstraction and hierarchical decomposition have long been recognized as a means, which enables complexity reduction on one side and problem decomposition to several subproblems of lower complexity on the other side. Structuring as a means to cope with complexity is more controversial and it seems there is no unisonous agreement about it. However, combining abstraction and hierarchical decomposition in the synthesis process assures only that the initial and subsequent system structures are replicated and impressed in solution system structure. On the other hand it is well known that contemporary systems are supported with an enormous amount of software, which directs their actions and is a strict consequence of systems' structuring. To visualize this we can imagine that software through execution connects an object-flow graph that corresponds to problem structure and behaviour. This means that structuring is already extensively used in system design. With respect to system represented with uncontrolled object-flow graph structuring requires three additional system structures. Its control structure directs subsystems , which can be at lowest representation level represented with uncontrolled object-flow graphs, connected in space and time. Particular strategy of , control used is of secondary importance. Its memory structure assures object validity during controlled execution. Transfer structure delivers objects to subsystems' inputs. Both memory and transfer structures are under control of control structure. Those structures are usually partitioned throughout the system following the principles of distribution and hierarchy. More intensive structuring results in complex control scheme, which is usually but not necessary expressed in a form of control code or software. Making software more close to human comprehension capabilities does not change its nature. However, it is interesting that structuring does not necessary impose any control code or software. This point of view allows that control code or software are determined as structuring side product. This Is a conclusion, which sounds quite heretic, however, it gives at least theoretical possibility for automatic software development. Basic structuring concept can be explained starting with a system with uncontrolled flow of objects. Observe that not all resources of such a system are active simultaneously. Assume a system in which resources are disconnected and a control mechanism, which Is capable to connect them in time and space. Under certain conditions behaviour of both systems can be identical. This simplified description, structuring is based on, should be completed with an observation that identical system resources can be shared when appropriate. To take advantage of this possibility system structure have to be completed with memory and transfer structures. If the behaviour of a system have to change, its control functions which determine resource connections will be appropriately modified. The simplest way to do this is through program memory, which is a part of system's control structure. Even when we look to software as problem description, system should be capable of its recognition and physical system restoration to solve the problem. A possible way to do this is that problem is represented with problems solvable with physical system resources. However, this introduce structure that have to be implemented with physical system in isomorphic way, directly or with appropriate time and space partition. System synthesis can now be conceptualized based on the problem expressed in a form of abstract system, which have to be transformed through hierarchical decomposition and structuring to a solution, a system expressed with resources and structure that can be implemented in physical .world. Problem solvability seems to be in tight connection with its representation. Different representations can be used to express particular view on the problem. They are equivalent In the sense that they express the same behaviour in different ways. Synthesis procedures proposed are defined for each representation. Change of one representation to another Is orderly developed. 1. OVERVIEW OF THE SYNTHESIS PROCESS Problem specification consists of two parts. Problem definition part determines an abstract system for which the synthesis process have to determine a solution expressed in the form of physical system specification to be implemented in predetermined technology domain. Behaviour of physical system can be recognized as behaviour of abstract system merely through the use of suitable abstraction, otherwise no relation exists between the systems. The rest of problem specification sets requests for the solution. Two classes, called the solution classes are determined based on the requests. Resource class consists of resource specifications, physical system should be built of. Resources determined with the resource class are generally composed and can be represented with resource structures of known behaviour. This usually allows resource class structuring through suitable relations. Abstraction through equivalence relation regarding resource behaviour reduces representation complexity and allows unnecessary details to be neglected at earlier synthesis steps. More sophisticated abstraction procedures to reduce representational complexity are described in section 3. Structure class consists of abstract resource structures. Physical system structure and its abstractions should be isomorphic to structures build of structures from structure class. Structure class is partially ordered with regard to substructure relation. Its representation complexity can be reduced through structure abstraction. Structure class can be empty. From the synthesis point of view this means that no structure requirements are set regarding the solution. Intuitively, abstract and physical systems can be delimited with the notion of distance, which is a measure proportional to the number of synthesis steps required to reach the solution. Its numeric determination provides estimate about problem complexity - P, NP complexity as the roughest measure, for example. An argument will be given to show that the synthesis problem belongs to the domain of NP - complete problems, in general. Initial synthesis steps must assure the match between problem and an abstract solution derived from solution classes. The match is found through structures' isomorphism and identical behaviour of corresponding resources. Further problem abstraction and structuring may be needed to assure it in explicit or implicit way. It is assumed, that some generic knowledge about problem solvability in the context of both solution classes is available. In the opposite case problem can be solved with an exhaustive search only. This is probably the strongest reason why a kind of systematic frame for the synthesis process is needed. Synthesis procedures cannot be deterministic because of partial ordering of structure class. Structure limitation can play a dominant role in limiting the number of synthesis steps. The other limiting factor for the synthesis step count can be searched for in resource class. Resource class consisting of resources with simple behaviour characteristics will necessary complicate the synthesis. With proper problem structuring and composite resources built of resources from resource class this problem can be reduced. However, the effect of this depends on knowledge about problem characteristic properties. Synthesis process can be stated as a combination of hierarchical problem decomposition and structuring. Hierarchical problem decomposition is a process basically opposite to abstraction. In our case it consists of refinement and interpretation processes. With its application problem is stepwise decomposed to a structure consisting of mutually dependent subproblems each of them have lower complexity with respect to the initial problem and subsequent subproblems obtained at earlier decomposition steps. This increases problem structure complexity and causes a consequence that structures of higher problem representation levels are replicated at lower representation levels. Applying structuring to arbitrary intermediate representation level results in structure change, while preserves representation level and behaviour. Since hierarchical decomposition preserves structure and structuring preserves representation level it is clear that requirements expressed through solution classes can be met only if both hierarchical decomposition and structuring are applied during the synthesis process. Synthesis process can be recognized as partial ordering relation between problem, intermediate solutions, and solution, where the solution or solutions are those intermediate solutions, which satisfy requests expressed through both solution classes. To find a path between -problem and solution and to avoid searching over the whole partially ordered structure of possible intermediate solutions, decisions based on their properties can drive the synthesis process. A minimal condition for an intermediate solution to be accepted for further synthesis is that it can be expressed with the objects of both solution classes. Different synthesis strategies can be used to determine the synthesis process. The simplest one and probably the less useful is one, where hierarchical decomposition to the resource class representation level is done first. This intermediate solution is then structured to assure compatibility with objects from structure class. However, structuring can become a task of excessive complexity within this approach. To avoid such situations, hierarchical decomposition and structuring are combined during the synthesis process. This assures manageable subproblems' complexity. Applying structuring and abstraction to both solution classes match between intermediate solution and structure consisted of objects from both solution classes can be found at each intermediate representation level. When such a match can be found between an intermediate solution and a structure consisting of objects from both solution classes without any abstraction such intermediate solution is accepted as a solution. Structures' isomorphism and identical behaviour of corresponding resources assure systems' equivalence. 2. REPRESENTATIONS Different views can be applied to represent the same system. In conventional one system is represented as a structure of interconnected resources with known behaviour. For system behaviour representation it is interesting to represent resource inputs with input positions and its outputs with output positions. Positions represent perception points from which object flow is oriented toward the resource or from it. For 4 two connected resources corresponding position plays double role. It is output position for one resource and input position for the other. Labelled bipartite directed graphs are suitable abstraction for this view on system's structure. System's behaviour can be represented with the behaviour of system resources. Based on resource positions collection of objects flowing to and from resource can be determined. Each collection corresponding to particular resource has objects represented with ; m + n tuples corresponding to objects on input and output resource positions. Such a collection can naturally be represented with function or relation, depending whether resource reacts to the same input in deterministic or nondeterministic way. Relation between functional and relational resource behaviour will be clarified later, in this section. During the synthesis process more attention can be given to system structure since its behaviour remains the same throughout this process. For this reason resource structure can be represented neglecting positions in system structure. Définition: Resource structure is labelled directed graph C = (V,E), where V = {Vj,...,ynl is a set of resources, and E = }cV x V is a set of resource connections. Resource labelling is defined with functions which assign labels to resources and connections and enable system behaviour recognition. Returning to the initial system model represented with bipartite directed graph it can easy be recognized that this representation is In close connection with data-flow graphs defined in [l] , [2] . In our case modification of this definition will be used for representing system's structure and behaviour. Definition: Controlled object-flow graph is labelled bipartite directed graph G = (AULUK, E), L fi K = O, A = {aj,...,a } is a set of action nodes, and LUK ={!•],...#lm, k1#...,k }. is a set of links, where K ={kj,...,k } is a set of control links. E C (A x (LUK) U (LUK) x A) is a set of branches defined so, that the following restrictions are satisfied, (a., Ik) e E & (a.. lk) € E =-,.ai = a., Ik e LUK, (lk, a.) € E & (lk, a.) € E a. = a,. Ik e LUK, l; .....Yj- Implement h^ with controlled function g^, •hQ (yf.....ym); p =1 l ; p = o. It can easy be verified that p, r, and q determine truth table for conditional. Corresponding controlled object - flow graph Is shown on figure 2.3. X1 9 *n controlled identical function Figure 2.3: Controlled object - flow graph representing conditional clause This representation allows inference processes' modelling in functional Way. Model of condition - action rule can be developed with slight modification of the above construction. Let R(x1# ... , xn) —►Q(x1, ... , xn, y), and Q(Xj, ... , xn, y) <ï=> (y = ... , xn)). Define characteristic function h for R, which defines domain of f. i 1 ; R(x., ... , x ) P = h(x.....x ) = | _2 l0 ; R(x,.....xn). and implement f with controlled function g, f fix, 9(P. x,.....xn) = | f(x,, ... , xn) ; p = 1 undef ; p = 0. Controlled object - flow graph that corresponds to the above construction is shown on figure 2.4. Figure 2.4: Controlled object - flow graph representing condition - action rule It Is Interesting to note that observing behaviour only on input and output links of a graph we are not able to identify whether function f is implemented directly or with function g. When dealing with systems it is usually presupposed that resources behave functionally. For systems described with relational connectives the above assumption may not be true. A minor modification allows that resources, which express relational behaviour can be treated in functional or relational way depending on point of view used. Since the complete treatment for arbitrary relations is relatively extensive, we will limit this presentation to binary relation R{x,y), which is partially closed with object a, R(a,y), R(x.y) a bj a b. i+1 a b l+i a b. i+n Applying object a to a resource, which behaves corresponding to R, its response will be nondeterministic since it can delivers any object from bj, bj+1, ... , b^n to its output position to satisfy R. The behaviour of a such resource can be represented in functional way, if resource response Is determined with a sequence function replacing R. Sequence function determines the order in which resource reacts with output objects to the same input determined with object a. Figure 2.5 gives tabular definition of sequence function and corresponding controlled object - flow graph for this case. Figure 2.5: Tabular definition of sequence function and corresponding controlled object - flow graph Identifiers 1 through 5 stand to identify functions fork, decision Boolean functions, controlled identical functions, function join, and memory function. Functions fork replicate input objects, decision Boolean functions control corresponding identical functions to deliver particular object bj+j to function join, which is a tres- hold function and delivers object bj+j to output link. Memory function assures necessary delay. Assumption k-1 is made that y has allways a value from bj,...,bj+n. Two notes are necessary about the above presentation. First, it is simplified to serve conception presentation only, and second, sequence function can be defined in a number of different ways. 3. REFINEMENT AND INTERPRETATION Using abstraction representation complexity can be reduced to a manageable level. During the synthesis process the situation is reversed, complexity grows, since this process is basically opposite to abstraction. Assume a solution system represented with resource structure and resource behaviour. Using a substructure relation to determine an arbitrary substructure observe that its behaviour can be described with collection of objects which correspond to its input and 7 output positions. This enables that substructure is replaced with a resource having input and output positions that correspond to substructure input and output positions. The replacement causes lower system structure complexity. Representing the system in each possible way with replacing substructures with resources while preserving their input output behaviour results in a class of systems with different structures and the same input output behaviour. An important hypothesis can be made at this point. System structure abstraction has sense only if the substructure behaviour can be expressed with its input output behaviour . Represent collections of objects which determine resources' behaviour with tables and assume they are of finite leught. Resource behaviour is represented with single table, while resource substructure behaviour is represented with a structure of interdependent tables. Select a pair resource, resource substructure with identical behaviour. The question arises whether the structure of interdependent tables can be developed based on the information obtained from single table. Results of empirical study show that this is possible. However, for a formal proof of the above claim additional research is needed. Results of mentioned study show that refinement based on the above concept is generally NP - complete problem since lower complexity bound grows exponentially with the number of table entries in non - trivial cases. Refinement is nondeterministic process that can be automated. Automatic algorithm development is possible. Controlled functions are necessary to obtain all possible refined versions of particular function. Refinement can be done on uncompletely specified tables. If this causes a lose of significant information, obtained algorithm will not be optimal. Example 3.1 gives tabular refinement for selected case of binary addition and corresponding controlled object - flow graphs, which have no control links for this case. Only one path of the whole refinement process is presented. Example 3.1 Loops and circles in resource substructure can introduce additional substructure inputs and outputs which are local to it. a1 b1 ao bo c2 d1 do 0 0 0 0 0 0 0 1 0 10 0 0 10 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 10 0 0 11 0 110 0 111 0 0 1 0 1 0 0 1 1 1 0 0 10 0 0 10 0 1 110 0 110 1 0 1 0 0 1 1 1 0 0 1 0 1 10 10 10 11 1110 1111 0 1 1 1 0 0 1 0 1 110 G: °2 d, "o Table T represents binary addition decompose to tables T.|, T2, and Tj, what results In the following controlled object - flow graph. V a1 b1 ao bo 1.step 2.step t M 0 0 0 1 \ -0—«— 1 ♦ \ ■+—0— 1 1 0 1 1 1 0 -e—e—&- -8—8—1- H—9—9- H—0—V- -«—f- -6—1—1- H—1—9- H—1— 11 ' ■1 a b 0 0 do 0 0 0 0 1 1 1 0 1 1 1 0 T1 becomes T^ after deleting redundant entries. 8 Corresponding controlled object - flow subgraph is reduced as represented below. ¿>1 32 21 V ao bo a1 b1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 -e—e- -e—i- H- -e—B- — 0 o 0 1 1 0 1 1 '21 ' a b c. 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 22' ^ T22 a1 b1 C1 d, 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 "l"2 is decomposed to T21 and T22. Corresponding controlled object - flow subgraph is refined as represented below. b1 ao b0 Refinement of Tj is analogous to the refinement of Tj. The result is. 32 ' a1 b1 C1 C2 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Controlled object - flow graph obtained after refinement of Tj, Tj, and T^ is given below. Because of close relation between tabular and expres-sionai function representation, the former can be thought of as tabular structure abstraction. Refinement procedures are generally developed for expressional function representation. Since this type of refinement is widely known its presentation will be avoided. 3.1 Function refinement This subsection states conditions that have to be satisfied with function refinement. Figure 3.1 shows graph of relations and controlled object - flow graphs for functions f and g, which is composition of functions gr ... , gr obtained through refinement. Refined function g and initial function f have to satisfy the relation f = h"1 o g o h, = g, and hj, h7 are identical functions. T31 = T21 ' 9 A^x ., AjX . x A x A B,x ... x B i n B.x ... x B 1 n a, o 9p- — 9r Figure 3.1: Function refinement Dependent of actual representation defined in section 2 function refinement is completed with corresponding graph refinement. Procedures for them can be found in [2] , [3] . Refinement can be thought of as a case of interpretation. However, we will give only basic definition and neglect this possibility. Figure 3.2 shows graphs of relations and corresponding controlled object - flow graphs when Interpreting function f with function g. When interpreting function f with function g the relation f = h^' o g o hj, where h1 and h2 are surjec-tive and possibly partial functions must be satisfied. Functions h1 and h2 assure compatibility with the environment. They can be stepwise removed with interpretation of environmental functions. Since h~1 is generally relation this can cause formal inconsistency with controlled object - flow graph behaviour. Since h^' can be represented with sequence function as illustrated in section 2 this can cause no serious problems. On the other hand h^ and h^ can be stepwise removed as mentioned above. The inconvenience can be avoided when h^ is bijective. 3.2 Object interpretation and refinement Until now objects were considered as integral units. However, for the reason of efficiency such observation is too restrictive. To avoid this, object representation can be adapted to problem representation level. Intuitively, an arbitrary object composed of several objects can be viewed as integral unit or as a structure 2 of objects positionally determined. In first case the fact that object is composed is neglected. Several objects must satisfy some known relation which determine their mutual positions to be recognized as integral unit . To represent such structures n - tuples are used. 3 Object refinement and interpretation are defined in connection with corresponding system's functions. Figure 3.3 shows a graph of relations and corresponding controlled object - flow graphs when refining objects of function f with objects of function g. -AjX C,x x A x C B,x D,x x B x D B A,x ... x A„-B,x ... x B_ 1 ml n a O a o- -o b Figure 3.2: Interpretation of f with g Figure 3.3: Object refinement and interpretation The notion of position is not restricted to physical position only. Difference between refinement and interpretation is semantical. Refinement is restricted to common semantic domain, while interpretation is not. 10 Object refinement and interpretation must satisfy, f = h^1 o go h2, where h1 and h2 are surjective and possibly partial functions. With further refinement functions h1 and h2 can be stepwise removed from the system. Object refinement and interpretation can be extended to objects from A^, ... , A , B^, ... » Bn> Stepwise refinement of an object results in a tree structure, an example of which is shown on figure 3.4. Figure 3.4: An example of object representation hierarchy Refinement and interpretation have an interesting property, they preserve structure of previous higher represantation levels. For illustration and application of this property assume an abstract system S1 and a physical system S2 and imagine both systems' behaviour in state spaces. Select an arbitrary state of S1 and with interpretation and refinement determine corresponding state of Sj. This state will cause in S2 a sequence of state changes. Assume a state from the sequence that has a corresponding state in S1 and assume that this state is next state of initially selected state of Sj. The impression an observer seeing only the states of S^ will have, is that S^ changes states altough in reality state changes of Sj are consequence of state changes in system S2> Figure 3.5 illustrates the above explanation. initiaj_ state initial state abstraction "S, ©next state next state abstraction sequence of state changes f q> i+1 Refinement and interpretation were defined for all representations given in section 2. More details about them can be found inC2] and C 3D • 4. STRUCTURING Assume arbitrary system represented with resource structure. Select a resource and denote it with r. Since system representation level can vary such resource can represent resource substructure of lower representation level. Determine those positions of system resource structure which carry objects from system Input positions to resource r input positions. In the resource structure positions determine resource substructure which input positions are part of system resource structure input positions, while its output positions comprise resource r input positions. For a subsystem, which belongs to the resource substructure determine composed relational expression denoted with E, which is satisfied when objects' state on resource r input positions enable resource activation. Instead with resource r function f determine its behaviour with relation corresponding to f and denote corresponding expression with Q. Form conditional E-*-Q, which is satisfied after resource r delivers objects on its output positions. In the context of structuring it will be called control condition, since it allows uniform determination of each subsystem's state which causes resource r action. Control condition can be rewritten as E—»-R 6 R —•• Q, where R denotes relational expression describing states on resource r input positions, which cause its action. This form of control expression enables associative approach to control. Determine characteristic function f£ for E, f£ : A Bool (a) = {1 ' ! I 0 : E o ; E, where A stands for subsystem's states and Bool determines (0, 1} . Characteristic function f£ will be interpreted as decision function since Its value decides about resource r activation. Implement resource r function f with controlled function g as described in section 2. Join functions f£ and g into a pair. Collection of such pairs determined for each system's resource enables system behaviour and its structure reconstruction. Figure 4.1 illustrates a distinction between the initial system and the system determined with collection of pairs decision function, controlled function. Figure 3.5: Implementation of Sj with S2 11 Figure 4.1: Distinction between systems Define in A equivalence relation such that all states which activate the same subsystem's resource and resource r belong to the same equivalence class. Actually, more than one resource can correspond to particular equivalence class. Denote the set of equivalence classes with A/R and define bijective function from A/R to Q, where Q stands for the set of states. Based on each state q from Q it can be uniformly determined which resource(s) have to be activated as a consequence of this state, because bijective connection between A/R and Q. Assume q from Q corresponds to equivalence class of states which causes resource r activation. Decision function corresponding to r can now be defined on set Q. To identify, when state q is active, what means that corresponding subsystem is In state which activates resource r, state transition function f : Q-»-Q is defined. It imitates subsystem state transitions from initial state to state corresponding to state q. This model of control can now be expressed with the relations, fs(s)=q, f£(q)=1, g(l, x,.....xj = f(x,.....xm), where s is the state preceeding state q, f£ is decision function, and g is controlled function corresponding to resource r function f. Process of control as described above, can be defined for arbitrary system resources. There are no restrictions to limit it to a single state transition function. Extension of the model that state transition function enables n-way branching including loop control is relatively simple and will not be considered here. State approach to control is not the only one that can be developed based on decision function. In fact, as far as recognized all popular control strategies and combinations of them can be developed on that base. One can easy recognize that if parts of control conditions are not necessary strictly distinct. This allows their logic composition, what results in decision function of the form, fg : A —— Boolk , k > 1. More than simple resource can be controlled with a decision function and consequently more resources can be controlled with state transition function as mentioned earlier. A pair decision function, controlled function enables structuring. A set of such pairs which determines the system can be partitioned to disjunctive subsets. The same effect can result from system partition on the set of disjunctive subsystems. System integration based on Its arbitrary partition can be realized in more different ways. Before do this we have to develop object transfer functions and memory functions. Transfer functions realize object transfer between positions, while memory functions assure that objects retain particular positions so long as determined with control structure. 4.1 Transfer functions Flow of objects between two arbitrary subsystems separated with a partition can be Implemented with selecting and distributive functions. Assume a subsystem which has to be connected to another subsystem over positions Pj, ... , pn- Denote sets of objects corresponding to positions with .....Xn, and let X = X, U ... U Xn- Selecting function IT is defined as, U : N x X. x ... x X —► X 1 n r x., 1 < i < n Ti(i, X ... , X ) = \ 1 undef, otherwise. The set of natural numbers N above can be replaced with arbitrary linearly ordered set. Indexes of Xj, ... , x become objects of such set. Linear ordering can be avoided If selecting function is defined in tabular form. Both approaches to define selecting operation can be mixed. Levels of indirection can be built to the above definition to determine particular position of n-tuple. Figure 4.2 shows controlled object - flow graph of selecting function. 12 subsystem Figure 4.2: Controlled object - flow graph of selecting operation Distributive function delivers objects obtained from selecting function to prespecified positions of a subsystem. Distributive function is defined as, 5 : N x X -Y1 x ... x Ym 4 r (undef,..., x,...,undef) ,yj=x, .....Ym)=5(i'x)=l 1- { n.j, n2 from N undef, otherwise. The value of x is represented in domain which is linearly ordered set. Because of simple notation the set of natural numbers was selected, otherwise a set of states can be used, since it is linearly ordered with the state transition function. In the real systems objects may have the ability to retain particular position - objects in mechanical systems for example have such property. However, since this is generally not true memory property have to be assured for objects not having this property. It is defined in recursive domain with the function, f : N x X -N x X ..1+1 * - J = f (x1) = x', n,< I < n2 Figure 4.3: Controlled object - flow graph of distributive function In the language of state transitions it has the ability to assure object position from current state to next state. This limitation can be removed with memory function control. Let p* be the value from Bool of decision function at i from N. Then, i+1 i i i fx''P,=1' n,< i < n, y = glp . v > = i i V. P "» i < n2. i i+k For k > 1 and p = 1 for particular i only, y will have the value of x', if i+k < n2. Extension to represent an object in time domain is straightforward and will not be considered here. Selecting and distributive functions can be composed to realize arbitrary complex networks, which are capable of transfering specified amount of objects in time and space. More requests for transfer than transfer paths available can exist simultaneously. Such requests are paid with appropriate time - space partition of transfer. Selecting and distributive functions are not the only transfer functions possible. However, they are 4 Recall a no object situation described in section 2. 4.3 Function representation in recursive domain System's behaviour can be represented in recursive domain when its functions are transformed to this domain. Similar extension in representation can be developed for time domain, continous or discrete. This allows synthesis in time domain. 13 Let f : X.x ... x X -- Y be a function to be 1 m represented in recursive domain. Define object interpretation functions. h. : N x X. x ... x X -1 1 m X. x ... x Xm l m h1 X1.....xn} " txi' •••' xm' ' Represent [i, x^..., xm) with (x^,..., x^), and define h1 (xï..... Xm> = h2 : N x Y h, (i, y) = y' (x xj; n,< i < n2 undef ; otherwise. Represent pair (i,y) with y1 and define, . . i. f y ; "1 < 1 < "2 h2 Cy) = \ 1 undef ; otherwise. Function f can now be represented in recursive domain with function g. g : NxXj* ... x X N x Y g (i, x,.....xm) = (i+1, y) or. g