2-Structures by Ehrenfeucht et al.

Have read through “Theory of 2-Structures” by Ehrenfeucht, Harju, Rozenberg, looking for clues towards Model Transformation. Here my little takeaway:

Theory of 2-Structures consists of 2 parts. The ‘static’ one, defining 2-Structures and Clans, is well summarized here: Introduction to 2-Structures by B. Krena (.ps). In the ‘dynamic’ part of the theory “Switch” is the fundamental concept:

Definition: Switch of a Graph
Let G1 = (D, E1) and G2 = (D, E2) be digraphs (directed graphs),
then G2 is said to be a Switch of G1, iff

it exists a binary labelling L: D -> {0, 1} s.t. L(d1) + [d1, d2]1 + L(d2) = [d1, d2]2,

where [d1, d2]i is 1 if (d1, d2) in Ei, else 0 and + is addition modulo 2.

1. E.g. For (d1, d2) in E1, L(d1) = 1 and L(d2) = 0 we have 1 + 1 + 0 = 0.
2. In plain words: opposite labelling switches the edge (else it remains).

Now 2-Structures theory is mainly concerned with analysing the algebraic properties of switches. Therefore Ehrenfeucht et al. give the following example:

Consider a network with a set of processors D, where each x in D is connected by a channel to each y in D for x neq y, and where each channel (x, y) may assume a certain value from a given set Δ , e.g., if Δ is {0, 1}, then the channels may be interpreted as having a sleeping and an active state; if Δ is the Reals, then the values can be considered as volumes of the channels.

For 3 Processors and channels setup as in (I) switches can be obtained by separating nodes into spots and circles, e.g. in the way it’s done subsequently (with 3 different starting points). Now, algebraic properties of these switches like commutativity etc can be considered, what can help understanding the behaviour of the processor network much better, as a basis for configuring it, testing it etc.

2-Structures - Example Switch

Beyond such ‘industrial’ examples I very much enjoy finding everyday cases where such formal concept apply (in most cases without noticing it). Haven’t found a nice one for switch yet. So in case someone has an idea, please let me know.

About modelpractice

Modeling Theory and Abstraction Awareness in strive for scientific rigour and relevance to information systems engineering.
This entry was posted in Mathematics and tagged , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to 2-Structures by Ehrenfeucht et al.

  1. Anonymous says:

    Think relations! There are many kinds and so many applications of relations. The theories of k-structures provide tools for understanding the nature of both the structure and the processes that can “act” on sets of relations. Switches are an example.

    • Hi
      Yes, totally agree, this is, the way to bring it down to earth. However, when you look at Ehrenfeucht’s book, it is classic def, theorem, proof Mathematics, without even giving justifications for the definitions. I.e. it doesn’t communicate the principles and understanding of the subject (seems to me it doesn’t even seem to care) and thus makes it quite hard to understand its relevance.
      So long

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s