Amalgamation

Beschreibung

Die Amalgation ist die Umkehroperation der Symbolspaltung. Wie man sich denken kann, werden hier zwei Symbole zu einem Symbol zusammengeführt.

Je nach Art der Symbolspaltung ist die Amalgamation auch unterschiedlich definiert:

• Für die Symbolspaltung nach Nachfolgern müssen die beiden Symbole $1_1,1_2$ die gleichen Vorgänger (Graph) und disjunkte Nachfolger (Graph) haben.
• Für die Symbolspaltung nach Vorgängern müssen die beiden Symbole $1_1,1_2$ die gleichen Vorgänger (Graph) und disjunkte Nachfolger (Graph) haben.

Die beiden genannten Amalgamationen haben analoge Eigenschaften.

Amalgation nach Nachfolger einer $\{0,1\}$-Matrix

Sei $X_B$ ein einseitiger Untershift endlichen Typs mit Alphabet $\{1_1,1_2,...,n\},p_B(1_1)=p_B(1_2)$ und disjunkte Nachfolger von $1_1,1_2$: $f_1\cup f_2=f$. Definiere einen Untershift $X_A$ mit Alphabet $\{1,...,n\}$ und den Transitionen $A$, die man durch Umkehrung des Symbolspaltens bekommt:

1. Erhalt der anderen Transitionen: Falls $j\ne 1$ und $1\notin f_A(j)$, dann $f_A(j)=f_B(j)$
2. Verschmelzen der Transitionen zu $1$:
   Falls $j\ne 1$ und $1\in f_A(j)$, dann $f_A(j)=f_B(j)-\{1_1,1_2\}\cup \{1\}$
3. Verschmelzen der Nachfolger ohne Selbstreferenz $f=f_1\cup f_2$: Falls $1_1$ und $1_2\notin f_B(1_r)$, dann $f_A(1)=f_B(1_1)\cup f_B(1_2)$
4. Verschmelzen der Nachfolger mit Selbstreferenz $f=f_1\cup f_2$: Falls $1_1$ oder $1_2\in f_B(1_r)$, dann $f_A(1)=f_B(1_1)\cup f_B(1_2)-\{1_1,1_2\}\cup \{1\}$

Obacht: Ich glaube das oben ist nicht ganz die richtige Definition für die Amalgamation. Wenn man weiter unten schaut, findet man die Eigenschaft, dass Amalgamationen kommutativ sind. Dies ist aber nicht ganz wahr, wenn bei drei Zuständen $1_1,1_2,1_3$ die Zustände $1_1,1_2$ und $1_2,1_3$ amalgamiert werden. Bei der zweiten Amalgamation müssen die Nachfolger nicht notwendigerweise disjunkt sein, was es nach der oberen Definition nicht möglich macht, eine Amalgamation durchzuführen. Erlaubt man aber, mehrfache Kanten zwischen Knoten, dann ergibt es Sinn, man man die Eigenschaft der Disjuktheit einfach weglassen kann. Die Amalgamation addiert einfach die Kanten. Indem Fall ist die Kommutativität wieder gegeben.

Wir präsentieren erst, wie sich die Amalgamation auf $\{0,1\}$-Matrizen auswirkt. Dann verallgemeinern wir das Vorgehen auf ${\mathbb{N}}_0$-Matrizen.

Charakterisierung als Amalgamation von Spalten

Sei $A$ eine ${\mathbb{N}}_0$-Adjazenzmatrix mit der Indexmenge $L_A=\{1_1,1_2,...,n\}$. Eine mögliche Amalgamation erkennt man daran, dass $1_1$ und $1_2$ gleiche Vorgänger aber disjunkte Nachfolger haben müssen. Für die Matrix bedeutet das, dass die Spalten gleich sind aber die Zeilen keine zwei Einsen in einer gemeinsamen Spalte haben dürfen. Durch Amalgamation von $1_1,1_2$ erhält man eine kleinere Matrix $B$. Die Matrix $B$ besitzt eine Zerlegung $B=SR$ in zwei $\{0,1\}$-Matrizen sodass $A=RS$.

$R$ hat Reihen, die durch $L_A$ indiziert sind und Spalten, die durch $L_B$ indiziert sind. Für $j\in L_B$ und

• $j\ne 1$ ist die $j$-te Spalte die gleiche wie bei $A$.
• $1$ ist die gleiche Spalte, wie die $1_1$ oder $1_2$-te Spalte von $A$ (die beiden Spalten sind gleich, da sie gleichen Vorgänger haben)

$R=\left(\begin{array}{cccc}{a}_{1_1{1}_1}& a_{1_{1}2}& ...& a_{1_{1}n}\\ a_{1_2{1}_1}& a_{1_{2}2}& ...& a_{1_{2}n}\\ a_{21_1}& a_{22}& ...& a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n{1}_1}& a_{1n}& ...& a_{nn}\end{array}\right)$ $S$ hat Reihen, die durch $L_B$ indiziert sind und Spalten, die durch $L_A$ indiziert sind. Für $j\in L_A$ und

• $j\ne 1_1,1_2$ hat die $j$-te Spalte eine $1$ im $j$-ten Feld und sonst eine $0$ (d.h, es ist die Identität)
• Die $1_1$ und $1_2$-te Spalte hat eine $1$ im $1$-ten Eintrag und sonst eine Null $S=\left(\begin{array}{ccccc}1& 1& 0& ...& 0\\ 0& 0& 1& & \\ ⋮& ⋮& & \ddots & \\ 0& 0& & & 1\end{array}\right)$

Obere Charakterisierung erhält den Namen, weil wir zwei gleiche Spalten zu einer vereinen. Es entspricht der disjunkten Vereinigung der Nachfolger mit gleichen Vorgängern. Es gibt eine einfache Möglichkeit, obere Methode für ${\mathbb{N}}_0$-Matrizen zu verallgemeinern. Wir lassen die Bedingung aus, dass die Nachfolger disjunkt sein müssen und addieren einfach die Zeileneinträge, d.h. wir erlauben Mehrfachkanten. Alles andere (einschließlich der Matrizen $S,R$) kann so bleiben.

Eigenschaften

Kommutativität von Amalgationen

Sei $A$ eine quadratische ${\mathbb{N}}_0$-Matrix und $X_A$ ein Untershift endlichen Typs. Seien $X_{B_1},X_{B_2}$ Untershifts, die man durch Amalgation erhält. Dann gibt es einen Untershift $X_C$, der aus Amalgation der anderen beiden hervorgeht. ren Bild illustriert (Obacht: Eine Kante zwischen $2_2$ und $4$ ist verkehrt) e Zustände $1_1,1_2$ werden in $X_{B_1}$ amalgamiert und die Zustände $2_1,2_2$ werden in $X_{B_2}$. Jetzt kann eine Fallunterscheidung durchgeführt werden:

• $1_1,1_2$ und $2_1,2_2$ sind verschieden: Amalgamiert man erst die $1$ und dann die $2$ oder umgekehrt erhält man den gleichen Untershift. Der Beweis nutzt, dass beide amalgamierten Zustände die gleichen Nachfolger haben.
• $1_1,1_2$ und $2_1,2_2$ haben einen Zustand gemeinsam: Amalgamiert man erst die $1$ und dann die $2$ oder umgekehrt erhält man den gleichen Untershift.

Aus der oberen Eigenschaft, folgert durch Induktion eine stärkere Eigenschaft.

Kleinste Amalgamation

Wenn $X_{B_1},X_{B_2}$ beide aus endlich vielen Amalgamationen von $X_A$ erhalten werden können, besitzen sie eine Folge von Amalgamation zu einem gemeinsamen Untershift $X_C$ nge folgt daraus die Existenz einer kleinsten Amalgamation (Siehe Totale Amalgamation).

SymbolicDynamicsOnesided2012]]