Models & Notation:

System Models - Dynamics in Graph Notation

system models (dynamics graphs)

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

[SuB] Norbert Bischof: Struktur und Bedeutung: Eine Einführung in die Systemtheorie; Verlag Hans Huber 1995.
[MB4] Mario Bunge: Ontology II: A World of Systems (Treatise on Basic Philosophy, Vol. 4); D Reidel Publishing 1979.
[PDI] Terence Pratt, Marvin Zelkowitz: Programmiersprachen: Design und Implementierung; Prentice Hall 1998.
[3KBH] Conrad Bock: Three Kinds of Behavioral Models; JOOP July/Aug 1999.

I. Quantity-Dependency Models

Black-Boxes: Input-Output Models
(Without internal structure or state, the graph is trivial.) The quantities in this case are n input terminals and m output terminals. The dynamics of black boxes is described by the relation between the values at the input and output terminals. The ``arrivals'' of value-changes at the input terminals and at the output terminals are principally concomittant (cf. arrows in flow charts show temporal order) [SuB 32]. Examples: deterministic discrete memoryless black boxes (described by a "transfer function" f: Inⁿ -> Out^m), probabilistic transfer, continuous steams of inputs and outputs (transfer function is a smooth function of time). The general equation relating inputs and outputs for n = m = 1 has the form:
output(t) = ^t_- dT M(t,T) F(input(T))

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.

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 xS_A×S_B, where S_A and S_B 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:

Syntropy's statecharts

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).
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].

(Timed) Message Passing Diagrams

navigation bar: Message-Passing
message passing diagrams
client-server architecture
object systems (model of computation)
message filtering systems
message passing meta-programming

show (temporally ordered and conditioned) flow of data packages (messages, e.g. events, operation requests, replies, ...) They do not show stepwise construction and transformation of data.
A. Messageflow diagrams show the flow of messages along connections between components (objects, subsystems, ...).

Syntropy's Mechanisms
UML's Collaboration diagrams

edge connection: path along which messages can flow from either end to the other
box (node) object: receives messages coming along whichever edge and sends messages along whichever edge
arrow data package: one message flowing along edge from tail-end to head-end; temporally ordered (by label)

cf. Event progress diagrams

B. Sequence diagrams show the temporal order of messages by vertical layout (-> objects become vertical lines)

ITU's Message Sequence Charts (MSC) (recommendation Z.120) is a graphical and textual language for the description and specification of the interactions between system components [my original link is broken]
UML's Sequence diagrams

IV. Mixed Models

Event Progress Diagrams
[ref]
box (node) o_s the object o in a certain state s
diamond (node) branch condition (as in flow chart)
arrow o_s -> q_t: 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

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 z₁ ... z_n. They can be described by an explicit equation for output x: "x=f'(z₁, ..., z_n)" [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

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. ...

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)