Models & Notation:

# System Models - Dynamics in Graph Notation

• modelling systems (introduction)
• system models (dynamics graphs)
• information models: spatial
• associative networks
•  back to: programming language design | paradigms | programming language list | signs | relations

 Remember that a system, in system theory, is a concrete section of the physical reality in which interactions take place, ie., processes run [SuB 13]. System theory, software engineering and computer science developed several ways of modeling computation and other processes, many of them in the form of directed graphs. These graph-based models of system(dynamic)s are centered around concepts like state, quantity, event/action (eg. transition), operand/data, operator/processor/actor: Quantity-dependency models [state-dimension ->value dependency<- state-dimension] visualize discretely (1) the quantities (variables, dimensions) of the system state [the partitioning of the state into dimensions is fixed] and (2) which quantities depend on which. Annotation (can) indicate (1) the current value of a quantity and (2) how the dependent quantities depend on others. The dynamics of the system lies in the propagation of quantity changes, which can be continuous (quantity-dependency models can model continuous systems). (The direction of change propagation is principally independent of the canalization of energy and matter flow: eg. water flows in the house through the water counter with count C via the tab with opening degree O into a bucket with fill hight F; the effect is not from C to O to F, but from O to C and to F [SuB 36].) Black box: Input/output models Mason diagrams Connectionist networks (perceptrons, neural networks) Control block diagrams - Taxonomy of control blocks State/event-order models [state(-of-a-state-dimension) ->temporal order<- event]: visualize discretely (1) the different states of the system or of all system state dimensions [how the state is partitioned into dimensions can change with the state] and (2) which state (of the system or dimension) is directly reachable from which other states (steps in time). Annotations can specify what type of event causes which state transition and what events are caused by such a transition. "pre-state" (internal pre-condition) + "input" (external cause) -> "output" (external effect) + "post-state". Black box: Trace models Flow charts Activity models (activity graphs, UML activity diagrams, Petri-nets) State machines: basic, Statecharts (orig., UML, Syntropy, RSML) - Taxonomy of flow charts Architectural models [piece-of-data ->patient|agent<- piece-of-process]: consist of subsystems (processing elements, processors), connectors (data channels), and data elements. [D. E. Perry and A. L. Wolf. Foundations for the study of software architecture. ACM SIGSOFT Software Engineering Notes, 17:40--52, October 1992] Process models (Untimed) dataflow models (Timed) message passing diagrams: messageflow diagrams (Syntropy's mechanisms, UML's collaboration diagrams) sequence diagrams (ITU's MSC, UML's sequence diagrams) Mixed models: Event progress diagrams - combines messageflow and state-transitions More system models? Cf. - Event-driven -> cf. multiagent models of computation and event-driven architecture - repository architecture

## I. Quantity-Dependency Models

Grey/Glas-Box models with (hypothetical/substantial) internal variables
 navigation bar: Coupling coupling relations / bonds quantity-dependency system models object change propagation systems object constraint programming
For comparison of the structured quantity-dependency models, let w,x,y,z be quantities, and let E,F,G,H be constraints between them.
 ``` F       (x)··········>(y)        ^ :        : :       : :     E : : G   : :   : :      : v       (w)<··········(z)             H  ```

 ``` .---------.   .-----. | F |   | (x)·|··|·····>(y)|   | ^ | `-------:-'   | : | :     |E : | .--:--.   `--:--' | : G|   : | : |   .--:-------. | v |   | (w)<·····|··|·(z) |   | H | `-----'   `----------'  ```

 ``` rd ##### set   (x)--># F #---(y)   ^ ##### |     set | v rd   ##### #####   # E # # G #   ##### #####   rd ^ | set  | ##### v     (w)<--# H #<--(z)    set ##### rd  ```
Mason diagrams   Connectionist networks/ graphs/ systems: perceptrons, artificial neural networks, ...   Control Block Diagrams (Blockschaltbild/Wirkungsplan)
Mason diagrams partition the state into quantities and show which quantity depends on which (Mason 1953) [SuB]
 circle (node) a variable quantity, an orthogonal piece of state (the system state is the assignment of a value to each quantity) arrow dependency = propagation of determination

If we assign the quantities to specific subsystems and then abstract from these quantities, we arrive at dependencies between subsystems, ie., -> couplings/bonds.
 ``` o·········>o    ^ :    : v    o<·········o    ```
 ```.-----. .-----. | o··|····|·>o | | ^ | | : | | · | | v | | o<·|····|··o | `-----' `-----'```
 ```.-----. .-----. | |···>| | | | | | | | | | | |<···| | `-----' `-----'```
Connectionist networks partition the system into nodes, each have one quantity as its state and one constraint to determine it from other quantities. Abstractly, dependency between the nodes' activations becomes dependency between the nodes, ie., -> couplings/bonds.
 unit (node) receives real-valued activity (excitatory/inhibitory) along its input lines. Has an output/state (activation) which changes depending on input (usually if sum reaches threshold). connection X -> Y means that «states of node X causally affect states of node Y» [Conn 17] (IOW, X and Y are -> coupled) The connection transmits X's activation to Y, modulating it depending on the connection's (modifyable) weight. (IOW, a connection is also a channel/connector, as in architectural models???)
They have two fundamentally different kinds of behavior:
• Synchronic behavior: determines output for input (nodes' activations change)
• Diasynchronic behavior: learning/training (connections' weights change) [Conn]
• Control block diagrams partition the system into transformers implementing the constraints (Mittelstaedt 1954) [SuB]
 block (node) constraint / stateless transformer from input to output signals ("subsystem", "channel", "Wirkung", "Steuerkörper", "Übertragungsglied") multi-arrow a variable quantity, whose change-determination (signal) flows from tails (writers) to heads (readers). The system state is the assignment of a value to each quantity.

 Taxonomy of Control Blocks (whether shown in control block diagrams or Mason diagrams) Explicit control blocks X0 (blocks of complexity 0, or type K(0)) have just one output x, and some inputs z1 ... zn. They can be described by an explicit equation for output x: "x=f'(z1, ..., zn)" [SuB]. Implicit control blocks have several outputs. ``` z1 _________ ---->| | : | | x : | X0 |---- ---->| | zn |_________| ``` Control blocks of complexity 1 (type K(1)) have two outputs x and y. A K(1) block X with only one input z can be specified by an implicit equation for outputs x and y: "z=f'(x,y)" [SuB]. There are five structurally different ways of decomposing X into two explicit control blocks F (for output x) and G (for output y) [SuB]: ``` _________ | | x z | |---- ---->| X | | |---- |_________| y ```

 chain ``` .·············>(x) : : (z) : v (y) ``` x=F(z)  i.e., z==>x, y-/->x y=G(x)  i.e., z=/=>y, x-->y ``` ............... : : x : .-->[F]---+-:---- z : | | : -----:-' .----' : : v : : [G]-----:---- :.............: y```
 loop ``` .·············>(x)<···. : : : (z) : : v : (y)····' ``` x=F(z,y)  i.e., z==>x, y-->x y=G(x)  i.e., z=/=>y, x-->y ``` ............... : : x : .-->[F]---+-:---- z : | ^-. | : -----:-' .--\-' : : v \ : : [G]---+-:---- :.............: y```
 fork ``` .·············>(x) : (z) : `·············>(y) ``` x=F(z)  i.e., z==>x, y-/->x y=G(z)  i.e., z==>y, x-/->y ``` ............... : : x : .-->[F]-----:---- z : | : -----:-| : : | : : `-->[G]-----:---- :.............: y```
 mesh ``` .·············>(x) : : (z) : : v `·············>(y) ``` x=F(z)  i.e., z==>x, y-/->x y=G(z,x)  i.e., z==>y, x-->y ``` ............... : : x : .-->[F]---+-:---- z : | | : -----:-| .----' : : | v : : `-->[G]-----:---- :.............: y```
 net ``` .·············>(x)<···. : : : (z) : : : v : `·············>(y)····' ``` x=F(z,y)  i.e., z==>x, y-->x y=G(z,x)  i.e., z==>y, x-->y ``` ............... : : x : .-->[F]---+-:---- z : | ^-. | : -----:-| .--\-' : : | v \ : : `-->[G]---+-:---- :.............: y```
where y-->x = "y controls x", i.e., a different value for y can change the value of x (negation: -|->).
and z==>x = "z controls x directly", i.e., arrows can be cut in a way that all other quantities (here: y) become constant without making x constant (negation: =|=>).

## II. State/Event-Order Models

 navigation bar: State-Transition transitional relationship state/event system models

 Black-Boxes: Trace Models (Without internal structure or state, the graph is trivial.) The only way to model the state/event-order without refering to internal states is by using as states the history of inputs and outputs of the system, the traces. ...

Visualize order of events: Flow charts
[Goldstine and John von Neumann 1946/47] [PDI]:
-> taxonomy of flow charts
 pill (node) an event/activity/process/"function" (specified by a label in the box), has one exiting arrow diamond (node) branch condition ("decision") with several exit arrows arrow temporal order = step in time ("transition") = "flow of control"

/\
|
highlight events
|

Events and states: Activity Models
 node A "activity" node B "state" arrow "stream"
Activity graphs that are: bi-partite, directed, relational (ie. unique edges between nodes in each direction)
They can be translated partially, but not totally, from/to dataflow diagrams.
[E.D. Falkenberg, R. van der Pols, and Th. P. van der Weide. Understanding process structure diagrams. Information Systems, 16(4):417-- 428, Sept 1991]

Activity diagrams (UML) are a generalization of the basic flow charts model where an activity diagram can model an events (process) in another, etc.

 column (spatial) with contained activities: the subsystem, component, object in which the activities take place ("swimlane") rounded box (node) an explicit state box (node) object, component, subsystem pointy/notched box (node) send/receive point: a signal is sent before successor starts / wait with successor until signal receit bar(pseudo-node of a multi-arrow) synchronization point: joining and forking of multiple threads of control dashed arrow message flow between objects, or signal flow between send/receive points

UML acitivity diagrams do not express object communication (ie., dataflow, cf. message flow) [3KBM]: «[I]t is a common mistake to assume [object operation] messages are passed between steps ... The method containing the step [in the activity diagram specifying it] coordinates the steps by defining their order and the conditions under which they are invoked, without making the operations in them dependent on each other.
An advanced technique to make the behavior model [expressed as activity diagram] object oriented is to associate each step with the changes to objects that the step is intended to cause, and associate those changes with the steps that they initiate.»

With multiple state actualizations: Petri Nets
(by Petri 1962) [ref]. Petri-nets are activity graphs whose states can be multiply actualized. (They are therefore useful in modelling systems with concurrent processes.) Multiple actualizations of a state (multiple "tokens" in a "place") is just a compact way of writing parallel sub-diagrams (cf. decompose state below) - but it places the emphasize not on how the state is decomposed but on which processes run concurrently. Also a Petri-net can be expanded to a normal state machine (???), but it may expand to an infinite state machine if the total number of actualizations is not limited.
 circle (node) a variable set of tokens ("place"), models conditions on transitions. The system state is the assignment of number of tokens to all the places. bar (node) event ("transition") arrow consumation of tokens from a place (arrow tail) by a transition (arrow head) or production of tokens in a place (arrow head) by a transition (arrow tail)
There have been many extensions to Petri's basic Petri-nets.
``SLANG is a domain-specific language for software process modeling and enactment, based on ER nets. ER nets are a high-level extensionm of Petri nets, that provide the designer with powerful means to describe concurrent and real-time systems. In ER nets, it is possible to assign values to tokens and relations to transitions, that describe the constraints on tokens consumed and produced by transition firings.'' [Sergio Bandinelli, Alfonso Fuggetta: Computational Reflection in Software Process Modeling: the SLANG Approach; 144-154 in SE'93]
 ``` |-->O-->|-->O-->| O---->| |---->O   |-->O-->|-->O-->| ```
 |highlight states|\/ /\|decompose process|
State machines, I/O automata, Statecharts, ...
 circle or rounded box (node) a discrete state of the system arrow temporal order = step in time ("transition") = an input/output/internal event (specified by a label on the arrow)
«Of all the grey box theories the simplest is perhaps automata theory ... In short, an automaton is a discrete and sequential system. ... Deterministic automata are of interest mainly in technology, where highly reliable systems are desirable. Probabilistic automata are of greater scientific and philosophical interest, for natural systems, such as brains and communities, are endowed with some spontaneity and seem to have strong stochastic components.
Automata are of greater interest than black box models because, unlike the latter, they take into account not only the behavior but also the internal states of the system. Consequently an automaton model can succeed ... where a black box model must fail ..., namely (a) when a stimulus elicits different responses depending on the state of the system [as far as it is not determined by the input history???], or (b) when the system has spontaneous (uncaused) outputs» [MB4 262].

|
decompose state
|
\/

With (varying) state dimensions
 ``` .----------------. | *->O--->O->(*) | O---->|················|---->O   | *->O--->O->(*) | `----------------' ```
In some (set of) system states, certain orthogonal factors (state-dimensions) may be distinguished, that can change (in part) independently. Without changing the underlying state machine, this can be exploited to structure the diagram: One region of a diagram is split into two (or more) parallel sub-diagrams A and B. This split can always be expanded to a set of product states xSA×SB, where SA and SB are the states of A and B, respectively, and corresponding transitions (a,b)->(a',b') and (a,b)->(a',b) and (a,b)->(a,b') for each transition a->a' of A and b->b' of B.
Statecharts [Harel 1985/87] are a generalization of the basic state machine model with
• decomposed states: "product states" (aka AND-states) [aggregation abstraction];
• sub/superstates [generalization abstraction] (this is actually a case of spatial information modelling, not of system modeling - cf. inclusion diagrams);
• guarding predicates for transitions.
The semantics was given in an operational way. Statecharts has many derivates:
1. Syntropy's statecharts
2. UML's Statecharts (with modifications to make them OO) have (1) composite states with concurrent or exclusive substates, (2) corresponding fork/join bars for transitions into/out-of concurrent substates, and (3) synchronization states between concurrent substates; (4) factored transition paths; and (5) submachines ("invocations" of state machines defined elsewhere).
3. RSML (with denotational/compositional semantics) [Heimdahl, Leveson: Completness and Consistency Analysis of State-Based Requirements; ACM/IEEE ICSE-17; ACM 1995]
 cf. Event progress diagrams

 Taxonomy of Flow Charts. A prime program is a minimal single entry, single exit flow chart graph which cannot decomposed into smaller minimal single entry, single exit flow chart subgraphs [PDI]. Maddux 1975 developed a theory of prime programs [PDI] based on a normal form of flow charts where function nodes [#] are single entry, single exit; decision nodes <%> are single entry, double exit; and with special joining nodes + which are double entry, single exit. Here is the list of prime programs with one to four nodes [PDI] (my appologies for the crude character graphics): 1 `---> [#]---> `basic side-effect (assignment, etc) 2 `---> [#]---> [#]---> `sequence ``` .-----v ---> <%> +---> `-----^ ```empty if (no effect) ``` .------.   v |   ---> *---> <%>--->  ```empty loop (no effect) 3 `---> [#]---> [#]---> [#]---> `triple sequence (superfluous)[why is it prime?] ``` .-----------v ---> <%> +---> `---> [#]---^ ```if-then ``` .--------------. v | ---> *---> [#]---> <%>---> ```do-while (repeat-until) ``` .---[#] <--. v | ---> *-------> <%>---> ```while-do 4 `---> [#]---> [#]---> [#]---> [#]---> `quadruple sequence (superfluous)[why is it prime?] ``` .---> [#]---v ---> <%> +---> `---> [#]---^ ```if-then-else ``` .-----[#] <----.   v |   ---> +---> [#]---> <%>---> ```do-while-do [PDI] ``` .-----------v ---> <%> .--> +---> +---> `---> <%>---------^ ``` useless (no effect) ``` .------------. v | ---> <%>--> +---> +---> <%>---> `-----------^ ``` conditional jump into empty loop (no effect) ``` .--------------. v | ---> +---> <%>---> <%>---> +---> `--------------^ ``` empty loop with exit (no effect) ``` .------------. v | ---> +---> +---> <%>---> <%>---> ^ | `--------------'```empty overlapping loops (no effect) ``` .------+ <-----. | ^ | v | | ---> +---> <%>---> <%>---> ```empty two conditions loops (no effect) ``` .----<%> <---. | | | v v | ---> +---> +---> <%>---> ```empty long/short loop (no effect)

## III. Architectural Models

A data element's transformers: Process Models
are the data view of architectures. They make explicit the data elements (look at their state properties, as far as relevant to the processors manipulating them), and which processor transforms one into the other (the "processing flow"); less emphasis is put on connectors than in dataflow models. [D. E. Perry and A. L. Wolf. Foundations for the study of software architecture. ACM SIGSOFT Software Engineering Notes, 17:40--52, October 1992]:
 arrow transformation (at tail: consumed data, at head: produced data), labeled with the processor performing the transformation node data element (the output of arrow-heads, the input to arrow-tails)

/\
|
from data elements' perspective
|

Processors and data elements
Diagrams showing both processors and data elements [but how are they called???]
- and processor/data hybrids - are popular, eg., in compiler construction:
 ``` _________ / source / """"||""" \/ ________ +-----------+ +------------+ / spec. /====>| Compiler |>====|/ Compiler /| """""""" | Generator | +------------+ +-----------+ \/ || ________ +-----------+ _________ / input /=======>|/ Applic. /|>===== / output / """""""" +-----------+ """"""""" ```

|
from processors' perspective
|
\/

A processors's data sources & sinks: (Untimed) Dataflow Models
 navigation bar: Dataflow agent/thing relation dataflow system models dataflow models of computation pipes & filters architecture
are the process view of architectures: They make explicit the processors (look at their functional properties: consumption->production, without looking into them), and the dataflow, i.e., the exchange (source->destination aka production->consumption) of discrete data packages between the processing elements. Dataflow models were made popular by DeMarco (1979) [according to ML1]. [D. E. Perry and A. L. Wolf. Foundations for the study of software architecture. ACM SIGSOFT Software Engineering Notes, 17:40--52, October 1992]:

A. Dataflow diagrams (DFD) [ML1] and [P.D. Bruza and Th. P. van der Weide. The semantics of data flow diagrams. In Proceedings of the International Conference on Management of Data, pages 66--78, 1989. Hyderabad, India.]
 arrow channel/pipeline through which data packages flow from tail to head (possibly typed) The system state is the assignment of a queque of data packages to each head of a pipeline. rounded box (node) data processor (computational component): takes a package from each input, and produces a package on each output open rectangle (node) data store (no direct flow from store to store) square (node) external entity (source, sink) diagram input and output (node) to made diagrams composable [ML1]
Can be translated partially, but not totally, from/to activity graphs [E.D. Falkenberg, R. van der Pols, and Th. P. van der Weide. Understanding process structure diagrams. Information Systems, 16(4):417-- 428, Sept 1991])

B. "Henderson" diagrams (shown to Sussman by Peter Henderson)
 multi-arrow pipeline through which data packages flow from each tail to all heads. The system state is the assignment of a queque of data packages to each head of a pipeline. box (node) data processor: takes a package from each input, and produces a package on each output triangle (a) (node) data constructor (special processor): multiple input (data components), single output (compound data) triangle (b) (node) data destructor (special processor): single input (compound data), multiple outputs (data components)
example taken here from [SICP].

## IV. Mixed Models

Event Progress Diagrams
[ref]
 box (node) os the object o in a certain state s diamond (node) branch condition (as in flow chart) arrow os -> qt: time flow (as in flow chart) +/- message passing (data flow): in state s the object o sends a message to q which puts q into state t. join bar (pseudo-node of a multi-arrow) only several messages together can put an object into the next state fork bar (pseudo-node of a multi-arrow) the sent message is multicast to several objects

 Location: http://www.cs.mun.ca/~ulf/pld/sysmod.html. Written 090602-050903 by Ulf Schünemann. Copyright (C) 2003 Ulf Schünemann.