Before formulation of some extensions of elementary cause-e ect (c-e) structures (see References), let us outline their concept by examples. A c-e structure (both elementary - a counterpart of 1-safe Petri nets - and extended) is a directed graph with predecessors and successors of every vertex (node) grouped into families of sets, as shows left graph in Fig.1: predecessors of e: ffa; bg; fb; cg; fdgg, successors: fff; gg; fhgg. In the right graph, the node sym-
bols are subscripted and superscripted with expressions called formal polynomials, that determine the grouping, so that the "operator of multiplication " collects the arguments into a group, whereas "operator of addition +" separates the groups. Symbol denotes the empty family. Thus, this graph is the set fae; be; ce; de; efa bg++bh c+d; f e; ge; heg. Each c-e structure can be represented by a set of such annotated nodes. The arrows, though helpful to understand its dynamics, are a super uous information. Informally, the dynamics is a "token game": node e can receive signals (represented by tokens) simultaneously from a and b or simultaneously from b and c or only from d, and send signals simultaneously to f and g or only to h. Thus, the operator " " means simultaneity, while "+" - exclusive choice. As a realistic example, consider the c-e structure ROAD in Fig.2, describing a tra c through the bridge B on the two-lane road, each lane for vehicles heading in the opposite directions. The bridge can hold only one vehicle at a time.
ROAD = fEE0 ; EBE0 ; BeE rr++wWl l; rB; eeB0 ; e0e; W W0 ; WBW 0 ; lB; wwB0 ; w0wg.
B B Anticipating the formal de nitions, notice that this is a combination ROAD = EW R + W E L, where EW = fEE0 ; EBE0 ; BeE ; eeB0 ; e0eg, W E = fW W0 ; WBW 0 ; BwW ; wwB0 ; w0wg, r = frBB,Brrg, l = f B lB,Bllg, or pictorially, a combination of the c-e structures in Fig.3. So, the "multiplication" and "addition" are now extended from the formal polynomials onto c-e structures, so that " " and "+" mean making union of sets being their arguments, with formal product and sum of subscripts/superscripts of nodes identically named in both sets. Now, the formal de nitions.
De nition 1 (set F [X], quasi semiring of formal polynomials) Let X be a non-empty enumerable set. Their elements, called nodes, are counterparts of places in Petri nets [Rei 85]. Let 2= X be a symbol called neutral. It will play a role of neutral element for operations on expressions, called formal polynomials over X. The names of nodes, symbol , operators +, and parentheses are symbols out of which formal polynomials are formed in the usual (in x) way. Their set is denoted by F [X]. Stronger binding of than +, allows for dropping some parentheses. Addition and multiplication of K; L 2F [X] is de ned as follows: K L = (K + L); K L = (K L). Let us use + and instead of and . It is required that the system hF [X]; +; ; i obeys the following equality axioms for all K; L; M 2 F [X]; x 2 X: (+) + K = K + = K ( ) K = K = K (++) K + K = K ( ) x x = x (+++) K + L = L + K ( ) K L = L K (++++) K + (L + M ) = (K + L) + M ( ) K (L M ) = (K L) M (+ ) If L 6= , M 6= then K (L + M ) = K L + K M Algebraic system which obeys these axioms will be referred to as a quasi-semiring of formal polynomials.3 The system hF [X]; +; ; i has a "family of sets" model shown above, thus is consistent. Its peculiarity, in contrast to the ordinary semiring, is axiom (+ ) the conditional distributivity of multiplication over addition, and the neutral for both operations. These assumptions make c-e structures behaviourally equivalent to Petri nets.
A cause-e ect structure (c-e structure) over X is a pair U = (C; E) of total and injective functions: C: E:
X ! F [X] X ! F [X] (cause function; nodes occuring in C(x) are causes of x) (e ect function; nodes occuring in E(x) are e ects of x) such that x occurs in the formal polynomial C(y) i y occurs in E(x). Carrier of U is the set car(U ) = fx 2 X : C(x) 6= _ E(x) 6= g. U is of nite carrier i jcar(U )j < 1 (j ::: j denotes cardinality). The set of all c-e structures over X is denoted by CE [X]. Since X is xed, we write CE - wherever this makes no confusion.
Since functions C and E are total, each c-e structure comprises all nodes from X, also the isolated ones - those from outside of its carrier. Presenting c-e structures graphically, only their carriers are pictured.
De nition 3 (addition and multiplication, monomial c-e structure) For c-e structures U = (CU ; EU ), V = (CV ; EV ) U + V = (CU+V ; EU+V ) = (CU + CV ; EU + EV ) (CU + CV )(x) = CU (x) + CV (x) U V = (CU V ; EU V ) = (CU CV ; EU EV ) (CU CV )(x) = CU (x) CV (x) de ne: where where 3 In the early papers on cause-e ect structures, the term "near-semiring" has been used. But in the meantime some authors used it in di erent meaning, so, we use term "quasi-semiring" for this axiomatic system. (The same symbol is used for multiplication of c-e structures, functions and polynomials) U is a monomial c-e structure i each polynomial CU (x) and EU (x) is a monomial, i.e. does not comprise non-reducible \+\.
Evidently U + V 2 CE and U V 2CE that is, in the resulting structures, x occurs in CU+V (y) i y occurs in EU+V (x) and the same for U V . Thus, addition and multiplication of c-e structures yield correct c-e structures.
The set CE with addition, multiplication and a distinguished element denoted also by and understood as the empty c-e structure ( ; ), where is a constant function (x) = for all x 2 X, makes an algebraic system similar to that in De nition 1.
The system hCE [X]; +; ; i obeys the following equations for all U; V; W 2 CE [X]; x; y 2 X: (+) + U = U + = U (++) U + U = U (+++) U + V = U + V (++++) U + (V + W ) = (U + V ) + W (+ ) If CV (x) 6= , CW (x) 6=
U (V + W ) = U V + U ( ) ( ) ( ) ( ) and EV (x) 6= W
U = U = U (x ! y) (x ! y) = x ! y
U V = V U U (V W ) = (U V ) W , EW (x) 6= then This follows directly from de nition of c-e structures and de nitions of adding and multiplying c-e structures. The operations on c-e structures make possible to combine small c-e structures into large ones.
De nition 4 (partial order ; substructure, set SUB [V ]) For U; V 2 CE let U V , V = U + V ; obviously, is a partial order in CE. If U V then U is a substructure of V ; SUB [V ]= fU : U V g is the set of all substructures of V . For A CE : V 2 A is minimal (w.r.t. ) in A i 8W 2 A: (W V ) W = V ) The crucial notion for behaviour of c-e structures is ring component, a counterpart of transition in Petri nets, i.e. a state transformer. It is, however, not a primitive notion but derived from the de nition of c-e structures, and is introduced regardless of any particular c-e structure:
De nition 5 ( ring component, set FC, pre-set and post-set) A minimal in CE nf g c-e structure Q = (CQ; EQ) is a ring component i Q is a monomial c-e structure and CQ(x) = , EQ(x) 6= for any x 2 car(Q). The set of all ring components is denoted by FC, thus the set of all ring components of U 2CE is FC [U ] = SUB [U ] \ FC. Following the standard Petri net notation, let for Q 2 FC and G FC : Q = fx 2 car(Q) : CQ(x) = g Q = fx 2 car(Q) : EQ(x) = g Q = Q [ Q (pre-set of Q) (post-set of Q) So, the ring component is a connected graph, due to the required minimality. Elements of the pre-set are its causes and elements of the post-set are its e ects. Of many conclusions from above de nitions, some are worth to point out:
Proposition 2 (a) U1 V1 ^ U2 V2 ) U1 + U2 V1 + V2 (monotonicity of +) (b) U (V + W ) U V + U W but equality not always holds (c) U V ) FC [U ] FC [V ] but converse implication not always holds (d) FC [U ] [ FC [V ] FC [U + V ] but converse inclusion not always holds Point (d) states that new ring components may appear when summing up c-e structures. For instance, let U = fax+y; bx y; xa b; ya bg, V = fax y; xa; yag, thus F C[U ] = ;, F C[V ] = fV g, F C[U + V ] = ffax; xag; fay; yag; V; fax y; bx y; xa b; ya bgg, thus F C[U ][FC [V ] 6=F C[U + V ]. The phenomenon of creation new ring components when assembling c-e structures from smaller parts, re ects a general observation: compound systems may sometimes reveal behaviours absent in their parts.
A state of c-e structure U is a total injective function s : car(U ) ! N!, thus a multiset over car(U ) (N! = N [ f!g, where ! symbolises in nity, that is ! > n for each n 2 N; N is the set of natural numbers, with 0). The set of all states of U is denoted by S.
De nition 7 (weights of monomials and capacity of nodes) Given a c-e structure U = (C; E) and its ring component Q 2FC [U ], let along with the pre-set Q and post-set Q of Q, some multisets Q: Q ! N!nf0g and Q : Q ! N!nf0g be given as additional information. The value Q(x) is called a weight (or multiplicity ) of monomial EQ(x) and the value Q (x) - a weight (or multiplicity ) of monomial CQ(x). Let cap be a total injective function cap : car(U ) ! N!, assigning a capacity to each node in the set car(U ). A c-e structure with such enhanced ring components is called a c-e structure-withweights of monomials and capacity of nodes.
De nition 8 ( ring components enabled and with inhibitors) For a ring component Q 2FC [U ], the set inh[Q] = fx 2 Q : Q(x) = !g is the collection of nodes in the pre-set of Q, whose e ect monomials EQ(x) are of weight !. The nodes in inh[Q] will play role of inhibiting nodes of ring component Q, as follows. For Q and state s let us de ne the formula: enabled[Q](s) d,ef 8x 2 inh[Q] : s(x) = 0^ 8x 2 Qninh[Q] : Q(x) 8x 2 Q : Q (x) + s(x)
s(x) cap(x)
cap(x)^ So, Q is enabled at the state s i none of inhibiting nodes x 2 Q contains a token and each remaining node in Q does, with no fewer tokens than is the weight of its e ect monomial EQ(x) and no more than capacity of each x 2 Q. Moreover, none of x 2 Q holds more tokens than their number, when increased by the weight of its cause monomial CQ(x); exceedes capacity of x. The inhibiting nodes of a ring components will be called its inhibitors. Fig.4(a) shows a ring component Q with weighted (multiplied) e ect monomials EQ(a) = 5 x, EQ(b) = ! (x y), EQ(c) = 3 y and weighted cause monomials CQ(x) = 2 (a b), CQ(y) = 4 (b c): The inhibitor of Q is node b. Fig.4(b) shows the behaviourally equivalent single transition in Petri net with weights and inhibitor arrow.
De nition 9 (semantics [[ ]] of c-e structures with inhibitors) For Q 2FC [U ] ; let [[Q]] S S be a binary relation de ned as: (s; t) 2 [[Q]] i enabled[Q](s) ^ t = (s Q) + Q cap (Q transforms state s into t). Semantics [[U ]] of U 2CE is [[U ]] = S [[Q]]. Closure, Q2FC [U] reachability and computation: (s; t) 2 [[U ]] i s = t or there is a sequence of states s0; s1; :::; sn with s = s0; t = sn and (sj ; sj+1) 2 [[U ]] for j = 0; 1; :::; n 1. State t is reachable from s in semantics [[ ]] and the sequenece s0; s1; :::; sn is a computation in U .
In the c-e structure which presents a ride throught the bridge B, the priority ride from the East can be enforced using inhibitor, i.e. node E in the pre-set of ring component fWB; E! B; lB; BW E lg, as shown in Fig.5.
Firing components fEB; rB; BE rg and fWB; E! B; lB; BW E lg of the ce structure in Fig.5 have Petri nets (with inhibitor arcs) counterparts as two transitions shown in Fig.6. A set of n sequential agents run concurrently under constraint: writing to a common le by the j th (j = 1; 2; :::; n) agent prevents all remaining from reading and writing, but not from their private (internal) activity. Reading may proceed in parallel. Fig.7 shows three agents with the following meaning of nodes: Aj agent of number j = 1; 2; 3 is active (holds a token) if it is neither reading nor writing; Rj - is active if the j th agent is reading; W j - is active if the j th agent is writing. W j and Rj play both roles: of the ordinary nodes or of the inhibitors, dependently which ring component they belong to.
Proposition 3
(a) U V )FC [U ] FC [V ] ) [[U ]] [[V ]] ) [[U ]] [[V ]] (b) [[U ]] [ [[V ]] [[U + V ]], but the reverse inclusion not always holds (c) FC [U ][FC [V ] =FC [U + V ] ) [[U ]] [ [[V ]] = [[U + V ]] but not conversely. (d) FC [U ][FC [V ] =FC [U + V ] and [[U ]] [ [[V ]] = [[U + V ]] are unrelated by implication.
Another extension: c-e structures with time.
Time models are di erent from those in Petri nets with time, where time is usually treated as necessary or admissible period of activity of a node (site or action). Here, the minimal time model is considered, where capacity of nodes equal 1, and with each node a time period of mandatory stay of a token is associated. This is the shortest time during which the node must hold the token. On expiry of this period, the token can leave the node (if other necessary conditions for this "move" are met). Lapse of time may be related either to individual ring components or to the whole c-e structure. The period of a token stay at a node is set up on entering this token into it and decreases by one time unit ("tick") of the timer referred to by the node, until permission to leave this node. On expiry of the mandatory residing time at this node, the token can leave it if all other conditions for this action are met. Any c-e structure with the minimal time model can be simulated ("implemented") by a c-e structure without time but with some additional nodes associated with every original node. A number of these supplementing and linearly ordered nodes represent duration of mandatory stay of a token in the original node.
U = hC; E; Tmini is a minimal-time c-e structure i hC; Ei c-e structure with capacity of nodes equal 1, and Tmin: car(U ) ! Nnf0g is a minimal time function of the meaning: Tmin(x) is the least number of time units indicated by a timer referred to by the node x, during which a token must stay at x since its appearance. The timer is associated to a particular node. The set of all the min-time c-e structures over is denoted by TminCE
De nition 11 (state of min-time c-e structure) State is a function s : X ! N with the informal meaning: s(x) = 0 if there is no token at the node x and s(x) > 1 is a remaining time (a number of ticks of the timer referred to by x) during which the token must remain at x; s(x) = 1 indicates that the time of compulsory residence of a token at the node x, prescribed by Tmin(x) has elapsed, thus, the token can be moved further - if other conditions for this are satis ed. The set of all states is S = NX (state-space).
So, now, the s(x) is not a number of tokens residing at the node, but a current time lapse.
For Q 2FC [U ]; let [[Q]] if and only if: S
8x 2 9x 2 Semantics [[U ]] of U 2 TminCE is the union of relations [[U ]] = Q : [s(x) = 1 ^ t(x) = 0 ^ 8y 2 Q : [s(y) = 0 ^ t(y) = Tmin(y)]_ Q : [s(x) > 1 ^ t(x) = s(x) 1] [[U ]] is the re exive and transitive closure of [[U ]]
S Q2FC [U] [[Q]].
The formula 9x 2 Q : [s(x) > 1 ^ t(x) = s(x) 1] expresses decrease by one time unit of token's stay at a certain node x of Q, if the minimal time of this token has not expired in the state s. The minimal time can be simulated by c-e structures without time constraints. An exemplary simulation of the c-e structure in Fig.8 ( ring component) depicts Fig.9. If the time is taken from a timer common to all nodes (violation of distributed systems' principles!), the semantics is re-interpreted: the decreasing elapse of time now concerns all nodes in car(U ), not only a given ring component. Thus, the formula 9x 2 Q : [s(x) > 1 ^ t(x) = s(x) 1] would be replaced with 9x 2 car(Q) : [s(x) > 1 ^ t(x) = s(x) 1]. An example of this case, taken from music, is in Fig.10.
Fig. 9. A possible simulation of the c-e structure in Fig.8 with the minimal time of nodes, by means of no-time c-e structure. The separate timer (each with perhaps diverse progress rate of time) is associated with every node. The counterclockwise direction of a token's motion inside the timers, simulates elapse of time controlled by the timers associated with nodes a; b; x; y.
The graphic examples have been tested by a computer program comprising editor and simulator of the cause-e ect structures [Chm 2003].
A number of problems and properties of extended c-e structures, not presented in this short note, can be transferred from elementary c-e structures (see References). For instance such issues as: { Decomposition of c-e structures { Relation to Petri nets and to other models of concurrency { C-e structures as lattices - their lattice properties { Processes generated by c-e structures, monoid of processes { Formal languages of c-e structure processes: the analysis and synthesis problems
Summarizing: the main motivation to develop the algebra (the quasi semiring) of c-e structures, was to combine structuring mechanism and transformation rules it provides, with appeal of simple pictorial and animated presentation of modelled real life systems. This algebra is a formal background for combining small c-e structures of easy to understand behaviour, into large system models, whose behavioral properties might be inferred from behaviour of their small parts. Such feature is called a compositionality (here conditional) - a counterpart of the extensionality in formal logic. Also, absence of explicit appearance of transitions and adjacent arrows - as is the case of Petri nets - provides more monitor space for graphic presentation. [Chm 2003] Chmielewski R. Symulacja struktur przyczynowo-skutkowych z wykorzystaniem platformy .NET (in Polish), MSc thesis, Warsaw University 2003 (Simulation of Cause-E ect Structures Using the .NET platform ) [Cza 98a] Czaja L. Cause-E ect Structures - Structural and Semantic Properties Revisited, FUNDAMENTA INFORMATICAE 33 (1998) pp. 17-42, IOS Press, Amsterdam [Cza 99] Czaja L. Representing Hand-Shake Channel Communication in the Calculus of Cause-E ect Structures, FUNDAMENTA INFORMATICAE, vol. 37, n. 4, March 1999, pp. 343-368 [Hol-Sza 88] Holenderski L., Szalas A. Propositional Description of Finite CauseE ect Structures, Information Proc. Letters 27 (1988), pp. 111-117 [Mag-Mat 97] Maggiolo-Schettini A., Matteuci G. Processes in Cause/E ect Systems, FUNDAMENTA INFORMATICAE 31 (1997) pp. 305-335, IOS Press,