ThinkArt Lab Hogmanay 2004
ThinkArt Lab Animation:  A.T. Kelemen
© November 12, 1998 Dr. Rudolf Kaehr

1 Computational Ontology and the Problem of Identity

Already Heraclitus pointed out that the notion of identity is not completly clear. But mathematicans prefer to proceed as if Heraclitus had not lived. I cannot continue in this way, this situation when an infinite process can be imbedded in an finite object is anordinary one in investigations of distinct natural number series, and I shall need an apparatus for the explicit consideration of all identifications used in such cases." A. Yessenin-Volpin

"Real-world computer systems involve extraordinarily complex issues of identity. Often, objects that for some purposes are best treated as unitary, single, or "one", are for other purposes better distinguished, treated as several.
Thus we have one program; but many copies. One procedure; many call sites. One call site; many executions. One product; many versions. One Web site; multiple servers. One url; several documents (also: several urls; one Web site). One file; several replicated copies (maybe synchronized). One function; several algorithms; myriad implementations. One variable; different values over time (as well as multiple variables; the same value). One login name; several users. And so on.
Dealing with such identity questions is a recalcitrant issue that comes up in every corner of computing, from such relatively simple cases as Lisp's distinction between eq and equal to the (in general) undecidable question of whether two procedures compute the same function.
The aim of the Computational Ontology project is to focus on identity as a technical problem in its own right, and to develop a calculus of generalized object identity, one in which identity -- the question of whether two entities are the same or different -- is taken to be a dynamic and contextual matter of perspective, rather than a static or permanent fact about intrinsic structure." Brian Cantwell Smith

By the way, what is static and what is dynamic may be in the eye of the beholder. `We suggest...that many grammatical frameworks are static formalizations of intuitively dynamic ideas´,.." Yuri Gurevich

Current OO notations make no distinction between intra-application variability, for example, variability of objects over time and the use of different variants of an object at different locations in an application, and variability between applications, that is, variability across different applications for different users and usage contexts."
K. Czarnecki, U. W. Eisenecker, Generative Programming

1.1 Identity

1.2 Equality


1.3 Bisimulation

By identifying two states with same external behavior, we get an extensional notion of equality, that can be captured by the following axiom:

Axiom 2.4. Two states are considered equal if they cannot be distinguished by (a combination of) observations.

To a user, again, the state may remain hidden, it is irrelevant, as long as the automaton implements the desired regular expression. Again, two states may be identified, if they behave the same way on the same input, which is to say, if they cannot be distinguished by any observation."


I am refering here to the great book Modal Logic (Blackburn et al.).

Bisimulation - the Basic Case

We first give the definition for the basic modal language.

Let M = (W, R, V) and M´= (W´, R`, V`) be two models.

A non-empty binary relation Z WxW`is called bisimulation between M and M`if the following conditions are satisfied:

(i)   If wZw`then w and w`satisfify the same letters.

(ii)  If wZw`and Rwv, then there exists v`(in M`)

      such that vZv`and R`w`v´ (the forth condition).

(iii) The converse of (ii): if wZw´and R`w`v`. then there exists v (in M) such that          vZv`and Rwv (the back condition).

Example:

The two models M und N are bisimilar.

Z = {(1,a), (2,b), (2,c), (3,d), (4,e), (5,e)}

Diagramm 1

Bisimilar Models

To show the bisimilarity of M and N, we define the relation Z. Condition (i) of our definition is satisfied: Z-related states make the same prpositional letters true. Moreover, the back and forth conditions are satisfied too: any move in M can be matched by a similar move in N, and conversely.

The two models are showing the same behavior in respect to the relation Z, therefore they are bisimilar.

"Quite simply, a bisimulation is a relation between two models in which related states have identical atomic information and matching possibilities."

"Examples of bisimulations (...) disjoint unions, generated submodels, isomorphisms, and bounded morphisms, are all bisimulations."

Bisimulation, Locality, and Computation

"Evaluating a modal formula amounts to running an automaton: we place it at some state inside a structure and let it search for information. The automaton is only permitted to explore by making transitions to neighboring states; that is, it works locally.

Suppose such an automaton is standing at a state w in a model M, and we pick it up and place it at state w´in a different model M´; would it notice the switch? If w and w´are bisimilar, no. Our atomaton cares only about the information at the current state and the information accessible by making a transition - it is indifferent to everything else. (...)

When are two LTS (Labelled Transition Systems) computationally equivalent? More precisely, if we ignore practical issues (...) when can two different LTSs be treated as freely exchangeable (óbservationally equivalent´) black boxes? One natural answer is: when they are bisimilar.

Bisimulation turns out to be a very natural notion of equivalence for both mathematical and computational investigations." p. 68

Morphograms and Bisimulation

We can now apply the idea of Bisimulation directly to our study of the behavior of morphograms in kenogrammatical systems.

For example, lets interprete morphogram MG = (aabcbcbaa) as Trito-Number TZ = (00121211).

Das Verhalten dieser Trito-Zahl ist jedoch nur über ihre Aktionen in beobachtbaren Systemen bzw. Kontexten zugänglich und diese seien hier ihre binären Komponenten.

Die Trito-Zahl TZ zeigt zwei Verhaltensweisen, die sich in zwei Modellen des Verlaufs der Binärsysteme darstellen lassen.

M = (S1122221) und N = (S1122211). M und N unterscheiden sich an der zweitletzten Stelle bzgl. S2 und S1. Die Knoten bzw. states der Modelle werden als die Belegungen des Morphograms durch Zahlen, d.h. der Trito-Zahl interpretiert. Die Zahlen als states haben einen Index, der angibt zu welchem Subsystem S1 oder S2 sie gehören bzw. den Übergang (Sprung) markieren.

Da das Morphogramm MG als solches nicht direkt zugänglich ist, dafür jedoch die zwei Modelle des Verhaltens des Morphograms, lässt sich aus der Bisimulation der zwei Modelle M und N auf die Struktur des Morphogramms schliessen. D.h. die Bisimulation zwischen M und N erzeugt eine Äquivalenz bzgl. des Verhaltens bzw. den Manifestationen des Morphogramms.

In dieser Thematisierung erscheint ein Morphogramm als die Klasse aller seiner bisimilaren Modelle. Nach der Terminologie von hidden und visible algebras, sind die beobachtbaren Verhaltensweisen des Morphogramms visible, und die dahinterliegende Struktur hidden.

Die zwei Trito-Zahlen TZ1= (001212) mit der Subsystemfolge S11222 und TZ2 = (001012) mit der Subsystemfolge S11112 sind nicht bisimilar, da die Wertung des 4. Zustandes in TZ1 und in TZ2 mit "2" bzw. "0" differieren.

1.4 Kenogrammatic decomposition and bisimulation

"Wenn sie in zwei gleiche Teile zerlegt werden können..." heisst, wenn ihre Verhaltenspattern sich nicht unterscheiden lassen, sind sie gleich. D.h., die Idee der Dekomposition eines Morphogramms in gleiche Monomorphien durch Abstraktion über verschiedenen Dekonstruktoren lässt sich als Bisimulation verstehen.

Es wird hier ein spezieller Zusammenhang zwischen der Struktur des Morphogramms und seines Verhaltens bei einer Dekomposition hergestellt.

Diagramm 2

EVk * Vs = EVs * Vk

Different questions (EVk, EVs), equal answers (ab, ab)

Diagramm 3

Modell von Selbigkeit-Gleichheit-Verschiedenheit

Diagramm 4

Identitäts-/Diversitäts-Relationen der Proto-Struktur

Diagramm 5

Unterschiede in der Gleichheit



ThinkArt Lab
http://www.ThinkArtLab.com
[email protected]