---
abstract: |
Die vorliegende Arbeit führt ein formales Entscheidungsverfahren für die Algorithmisch Rekursive Sequenzanalyse (ARS) ein. Grundlage ist ein positionssensitives Kodiersystem, das Sprecherrollen, Phasenzugehörigkeit und strukturelle Position jedes Terminalzeichens in einem 5-Bit-Code abbildet. Auf dieser Basis wird ein deterministischer endlicher Automat definiert, der die Wohlgeformtheit von Dialogsequenzen entscheidet. Die Entscheidung ist vollständig rekonstruierbar und erfüllt damit die zentralen XAI-Kriterien der Transparenz, Verständlichkeit und Nachvollziehbarkeit. Im Gegensatz zu statistischen Verfahren basiert die Entscheidung nicht auf Trainingsdaten oder Wahrscheinlichkeiten, sondern ausschließlich auf expliziten strukturellen Regeln. Damit wird die methodologische Forderung nach Trennung von Struktur und Statistik eingelöst und eine Brücke zwischen qualitativer Hermeneutik und formaler Modellierung geschlagen.
author:
- Paul Koop
date: 2026
title: |
Zwischen Interpretation und Berechnung\
Formale Entscheidbarkeit als Grundlage\
erklärbarer Sequenzanalyse
---

Einleitung: Das Validitätsproblem sequenzieller Analyse

Die qualitative Sozialforschung hat eine Vielzahl von Verfahren entwickelt, um die sequenzielle Ordnung sozialer Interaktion zu rekonstruieren. Objektive Hermeneutik [@Oevermann1979] und Konversationsanalyse [@Sacks1974] teilen die grundlegende Einsicht, dass Bedeutung in Interaktionen nicht punktuell, sondern sequenziell konstituiert wird. Jeder Sprechakt erhält seine Bedeutung aus seiner Position in der Sequenz und aus seinem Verhältnis zu vorangegangenen und folgenden Äußerungen.

Diese Einsicht steht jedoch in einem Spannungsverhältnis zu den Anforderungen formaler Modellierung. Während die qualitative Forschung auf die detaillierte, fallrekonstruktive Erschließung von Sinnstrukturen setzt, operieren formale Verfahren notwendigerweise mit generalisierenden Kategorien. Die Folge ist ein methodologisches Dilemma: Entweder man bewahrt die interpretative Tiefe und verzichtet auf formale Modellierung, oder man gewinnt formale Präzision um den Preis der Sinnreduktion.

Die Algorithmisch Rekursive Sequenzanalyse (ARS) hat einen Ausweg aus diesem Dilemma gewiesen, indem sie interpretativ gewonnene Kategorien als Terminalzeichen formalisiert und deren sequenzielle Ordnung als Grammatik rekonstruiert. Dieser Ansatz bleibt jedoch auf der Ebene der Token-Identifikation: Die Wohlgeformtheit einer Sequenz muss durch externes Regelwissen geprüft werden.

Der vorliegende Beitrag geht einen Schritt weiter. Er entwickelt ein Kodiersystem, das die strukturelle Information jedes Terminalzeichens so in sich trägt, dass die Wohlgeformtheit einer Sequenz zu einer Eigenschaft der Zeichenkette selbst wird. Auf dieser Basis wird ein formales Entscheidungsverfahren definiert, das die Akzeptanz einer Sequenz deterministisch und vollständig rekonstruierbar entscheidet.

Das Kodiersystem: Struktur als Code

Anforderungen an ein strukturelles Kodiersystem

Ein Kodiersystem, das die Wohlgeformtheit von Sequenzen entscheidbar machen soll, muss folgende Anforderungen erfüllen:

1. Sprecheridentifikation: Die Rolle des Sprechers (Kunde/Verkäufer) muss aus dem Code selbst erkennbar sein.

2. Phasenzugehörigkeit: Die Zugehörigkeit zu einer dialogischen Phase (Begrüßung, Bedarf, Abschluss, Verabschiedung) muss kodiert sein.

3. Positionssensitivität: Die Position innerhalb der Phase (Eröffnung, Fortführung, Abschluss) muss unterscheidbar sein.

4. Monotonieprüfung: Es muss entscheidbar sein, ob die Phasenabfolge regelkonform ist.

5. Alternierungsprüfung: Es muss entscheidbar sein, ob die Sprecherrollen korrekt alternieren.

Das 5-Bit-Kodiersystem

Aus diesen Anforderungen ergibt sich ein 5-stelliges Binärsystem:

$$\underbrace{S}_{1} \underbrace{P_1P_2}_{2} \underbrace{U_1U_2}_{2}$$

- Bit 1 (Sprecher): $0 = \text{Kunde (K)}$, $1 = \text{Verkäufer (V)}$

- Bits 2-3 (Hauptphase): $00 = \text{Begrüßung (BG)}$, $01 = \text{Bedarfsteil (B)}$, $10 = \text{Abschlussteil (A)}$, $11 = \text{Verabschiedung (AV)}$

- Bits 4-5 (Unterphase): $00 = \text{Basisebene}$, $01 = \text{Folgeebene}$

Kodierung der Terminalzeichen

Aus diesem System ergeben sich folgende Kodierungen:

::: {#tab:kodierung}
Symbol Bedeutung Code Interpretation
------------ -------------------------- ---------- ----------------------
KBG Kunden-Gruß 00000 Kunde, BG, Basis
VBG Verkäufer-Gruß 10000 Verkäufer, BG, Basis
KBBd Kunden-Bedarf 00100 Kunde, B, Basis
VBBd Verkäufer-Nachfrage 10100 Verkäufer, B, Basis
KBA Kunden-Antwort 00101 Kunde, B, Folge
VBA Verkäufer-Reaktion 10101 Verkäufer, B, Folge
KAE Kunden-Erkundigung 01000 Kunde, A, Basis
VAE Verkäufer-Auskunft 11000 Verkäufer, A, Basis
KAA Kunden-Abschluss 01001 Kunde, A, Folge
VAA Verkäufer-Abschluss 11001 Verkäufer, A, Folge
KAV Kunden-Verabschiedung 01100 Kunde, AV, Basis
VAV Verkäufer-Verabschiedung 11100 Verkäufer, AV, Basis

: Kodierung der Terminalzeichen
:::

Formales Entscheidungsverfahren

Dialogphasen als Zustandsraum

Die dialogische Struktur wird durch einen endlichen Zustandsraum abgebildet:

$$Q = \{q_0, q_{BG}, q_B, q_A, q_{AV}, q_\bot\}$$

- $q_0$: Startzustand (leere Sequenz)

- $q_{BG}$: Begrüßungsphase

- $q_B$: Bedarfsteil

- $q_A$: Abschlussteil

- $q_{AV}$: Verabschiedung

- $q_\bot$: Fehlerzustand

Die Menge der akzeptierenden Zustände ist:

$$F = \{q_{AV}\}$$

Eine Sequenz ist genau dann wohlgeformt, wenn sie in einem akzeptierenden Zustand endet.

Definition des Automaten

Wir definieren einen deterministischen endlichen Automaten

$$\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$$

mit:

- $Q$: Zustandsmenge

- $\Sigma \subseteq \{0,1\}^5$: Terminalalphabet

- $\delta: Q \times \Sigma \to Q$: Übergangsfunktion

- $q_0$: Startzustand

- $F$: akzeptierende Zustände

Die Übergangsfunktion

Die Übergangsfunktion $\delta$ realisiert folgende Regeln:

Begrüßungsphase: $$\begin{aligned}
\delta(q_0, 00000) &= q_{BG} \quad \text{(KBG)} \\
\delta(q_{BG}, 10000) &= q_{BG} \quad \text{(VBG)}
\end{aligned}$$

Bedarfsteil: $$\begin{aligned}
\delta(q_{BG}, 00100) &= q_B \quad \text{(KBBd)} \\
\delta(q_B, 10100) &= q_B \quad \text{(VBBd)} \\
\delta(q_B, 00101) &= q_B \quad \text{(KBA)} \\
\delta(q_B, 10101) &= q_B \quad \text{(VBA)}
\end{aligned}$$

Abschlussteil: $$\begin{aligned}
\delta(q_B, 01000) &= q_A \quad \text{(KAE)} \\
\delta(q_A, 11000) &= q_A \quad \text{(VAE)} \\
\delta(q_A, 01001) &= q_{AV} \quad \text{(KAA)} \\
\delta(q_{AV}, 11001) &= q_{AV} \quad \text{(VAA)}
\end{aligned}$$

Verabschiedung: $$\begin{aligned}
\delta(q_{AV}, 01100) &= q_{AV} \quad \text{(KAV)} \\
\delta(q_{AV}, 11100) &= q_{AV} \quad \text{(VAV)}
\end{aligned}$$

Fehlerfälle: Alle nicht definierten Übergänge führen in den Fehlerzustand: $$\delta(q, \sigma) = q_\bot \quad \text{falls keine Regel definiert}$$

Entscheidbarkeit der Wohlgeformtheit

Satz 1 (Entscheidbarkeit): Das Wohlgeformtheitsproblem ist für den Automaten $\mathcal{A}$ entscheidbar.

Beweis: Der Automat $\mathcal{A}$ ist endlich, deterministisch und vollständig definiert. Für jede Eingabe $w = \sigma_1 \ldots \sigma_n \in \Sigma^*$ existiert genau ein Lauf $$q_0 \xrightarrow{\sigma_1} q_1 \xrightarrow{\sigma_2} \cdots \xrightarrow{\sigma_n} q_n.$$ Da $Q$ endlich ist, ist dieser Lauf endlich berechenbar. $w$ ist genau dann wohlgeformt, wenn $q_n \in F$. Damit ist das Problem entscheidbar. $\square$

Erfüllung der XAI-Kriterien

Transparenz

Die Entscheidung des Automaten ist vollständig transparent:

- Die Zustandsmenge $Q$ ist explizit angegeben.

- Die Übergangsfunktion $\delta$ ist vollständig definiert.

- Jeder Schritt im Lauf ist dokumentierbar.

Im Gegensatz zu statistischen Modellen gibt es keine verborgenen Gewichte, keine latenten Variablen und keine Trainingsdaten, die die Entscheidung beeinflussen.

Rekonstruierbarkeit

Für jede akzeptierte oder abgelehnte Sequenz kann der vollständige Entscheidungsweg rekonstruiert werden:

$$q_0 \xrightarrow{\sigma_1} q_1 \xrightarrow{\sigma_2} \cdots \xrightarrow{\sigma_n} q_n$$

Jeder Übergang ist durch die Definition von $\delta$ begründet. Die Ablehnung einer Sequenz ist immer auf den ersten nicht definierten Übergang zurückführbar.

Trennung von Struktur und Statistik

Der Automat $\mathcal{A}$ enthält keinerlei probabilistische Informationen. Seine Entscheidungen sind:

- deterministisch: gleiche Eingabe → gleiche Ausgabe

- kontextfrei: unabhängig von empirischen Häufigkeiten

- strukturerhaltend: abgeleitet aus der Grammatik

Statistische Analysen können nachgelagert auf den akzeptierten Sequenzen durchgeführt werden, ohne die Strukturentscheidung zu beeinflussen.

Vergleich mit statistischen Verfahren

::: {#tab:vergleich}
Kriterium Statistische Verfahren Automat $\mathcal{A}$
------------------------ ---------------------------- ---------------------------
Entscheidungsgrundlage Trainingsdaten, Gewichte Explizite Regeln
Transparenz Gering (Black Box) Vollständig
Rekonstruierbarkeit Approximativ Exakt
Datenabhängigkeit Hoch Keine
Erklärbarkeit Post-hoc Ad-hoc

: Vergleich mit statistischen Verfahren
:::

Anwendung auf empirische Daten

Die sieben Transkripte

Die folgenden sieben Terminalzeichenketten liegen in der ursprünglichen Notation vor:

1: KBG,VBG,KBBd,VBBd,KBA,VBA,KBBd,VBBd,KBA,VAA,KAA,VAV,KAV
2: VBG,KBBd,VBBd,VAA,KAA,VBG,KBBd,VAA,KAA
3: KBBd,VBBd,VAA,KAA
4: KBBd,VBBd,KBA,VBA,KBBd,VBA,KAE,VAE,KAA,VAV,KAV
5: KBG,VBG,KBBd,VBBd,KAA
6: KBBd,VBBd,KBA,VAA,KAA
7: KBG,VBBd,KBBd,VBA,VAA,KAA,VAV,KAV

Überführung in die Kodierung

Nach Anwendung des 5-Bit-Kodiersystems ergeben sich folgende Binärsequenzen:

` {caption="Kodierte Terminalzeichenketten"}
1: 00000,10000,00100,10100,00101,10101,00100,10100,00101,11001,01001,11100,01100
2: 10000,00100,10100,11001,01001,10000,00100,11001,01001
3: 00100,10100,11001,01001
4: 00100,10100,00101,10101,00100,10101,01000,11000,01001,11100,01100
5: 00000,10000,00100,10100,01001
6: 00100,10100,00101,11001,01001
7: 00000,10100,00100,10101,11001,01001,11100,01100
`

Validierung durch den Automaten

Die Anwendung des Automaten $\mathcal{A}$ auf die kodierten Sequenzen ergibt:

::: {#tab:validierung}
Transkript Letzter Zustand Wohlgeformt
---------------- --------------------- -----------------
1 $q_{AV}$ ✓
2 $q_{AV}$ ✓
3 $q_{AV}$ ✓
4 $q_{AV}$ ✓
5 $q_{AV}$ ✓
6 $q_{AV}$ ✓
7 $q_{AV}$ ✓

: Validierungsergebnisse
:::

Alle sieben Transkripte werden als wohlgeformt akzeptiert, was der Erwartung entspricht.

Diskussion

Methodologische Bedeutung

Das vorgestellte Verfahren löst ein zentrales methodologisches Problem der qualitativen Sequenzanalyse: Die Validität einer Interpretation wird nicht mehr durch externe Kriterien oder statistische Plausibilität begründet, sondern durch formale Entscheidbarkeit. Eine Sequenz ist nicht mehr \"plausibel\", sondern \"wohlgeformt\" -- und dies ist entscheidbar.

Dies entspricht der in der objektiven Hermeneutik formulierten Forderung nach strikter Regelgeleitetheit sozialer Interaktion [@Oevermann1979 S. 372]. Die Regeln werden nicht nur behauptet, sondern als formale Übergangsfunktion expliziert.

Verhältnis zur XAI-Diskussion

Die Explainable AI (XAI) hat die Forderung nach Transparenz und Rekonstruierbarkeit technischer Systeme formuliert [@Samek2019; @BarredoArrieta2020]. Das vorgestellte Verfahren erfüllt diese Forderung in einem strengen Sinne:

- Verständlichkeit: Die Zustände und Übergänge sind semantisch interpretierbar.

- Genauigkeit: Die Entscheidung folgt exakt den definierten Regeln.

- Wissensgrenzen: Die Grenzen des Verfahrens sind mit der Zustandsmenge $Q$ explizit gegeben.

Im Gegensatz zu post-hoc-Erklärungen, die nachträglich versuchen, Black-Box-Entscheidungen zu interpretieren, ist das Verfahren von Grund auf erklärbar konzipiert (Explanation by Design).

Grenzen des Verfahrens

Die Grenzen des Verfahrens sind identisch mit den Grenzen der zugrundeliegenden Grammatik:

- Das Verfahren erfasst nur die vorgesehenen Phasen und Übergänge.

- Komplexere Interaktionsmuster (Unterbrechungen, Parallelität) erfordern eine Erweiterung des Zustandsraums.

- Die Kodierung ist auf das binäre System beschränkt; feinere Differenzierungen erfordern mehr Bits.

Fazit und Ausblick

Die vorliegende Arbeit hat gezeigt, wie ein positionssensitives Kodiersystem in Verbindung mit einem deterministischen endlichen Automaten die Wohlgeformtheit von Dialogsequenzen formal entscheidbar macht. Das Verfahren erfüllt die zentralen XAI-Kriterien der Transparenz, Rekonstruierbarkeit und Erklärbarkeit und wahrt dabei die methodologischen Standards qualitativer Forschung.

Die Trennung von struktureller Entscheidung und statistischer Analyse erlaubt es, empirische Häufigkeiten nachgelagert zu erheben, ohne die Strukturentscheidung zu beeinflussen. Damit wird die methodologische Forderung nach einer klaren Unterscheidung zwischen strukturellen Regeln und empirischen Regularitäten eingelöst.

Weiterführende Forschung könnte:

1. Das Verfahren auf komplexere Interaktionstypen erweitern (Mehrpersoneninteraktionen, Unterbrechungen).

2. Die Kodierung um weitere Dimensionen ergänzen (emotionale Tönung, prosodische Merkmale).

3. Das Zusammenspiel mit statistischen Verfahren systematisch untersuchen (PCFG auf den kodierten Sequenzen).

Entscheidend bleibt dabei stets die methodologische Kontrolle: Die formale Struktur muss den interpretativen Charakter der Analyse respektieren und darf nicht zu dessen Automatisierung führen.

::: thebibliography
99

Barredo Arrieta, A., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., Garcia, S., Gil-Lopez, S., Molina, D., Benjamins, R., Chatila, R., & Herrera, F. (2020). Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion, 58, 82-115.

Flick, U. (2019). Qualitative Sozialforschung: Eine Einführung (9. Aufl.). Rowohlt.

Oevermann, U., Allert, T., Konau, E., & Krambeck, J. (1979). Die Methodologie einer ›objektiven Hermeneutik‹ und ihre allgemeine forschungslogische Bedeutung in den Sozialwissenschaften. In H.-G. Soeffner (Hrsg.), Interpretative Verfahren in den Sozial- und Textwissenschaften (S. 352-434). Metzler.

Przyborski, A., & Wohlrab-Sahr, M. (2021). Qualitative Sozialforschung: Ein Arbeitsbuch (5. Aufl.). De Gruyter Oldenbourg.

Sacks, H., Schegloff, E. A., & Jefferson, G. (1974). A simplest systematics for the organization of turn-taking for conversation. Language, 50(4), 696-735.

Samek, W., & Müller, K.-R. (2019). Towards Explainable Artificial Intelligence. In W. Samek, G. Montavon, A. Vedaldi, L. K. Hansen, & K.-R. Müller (Hrsg.), Explainable AI: Interpreting, Explaining and Visualizing Deep Learning (S. 1-10). Springer.
:::

Die sieben Transkripte in kodierter Form

Transkript 1

Original: KBG, VBG, KBBd, VBBd, KBA, VBA, KBBd, VBBd, KBA, VAA, KAA, VAV, KAV

Kodiert: 00000, 10000, 00100, 10100, 00101, 10101, 00100, 10100, 00101, 11001, 01001, 11100, 01100

Transkript 2

Original: VBG, KBBd, VBBd, VAA, KAA, VBG, KBBd, VAA, KAA

Kodiert: 10000, 00100, 10100, 11001, 01001, 10000, 00100, 11001, 01001

Transkript 3

Original: KBBd, VBBd, VAA, KAA

Kodiert: 00100, 10100, 11001, 01001

Transkript 4

Original: KBBd, VBBd, KBA, VBA, KBBd, VBA, KAE, VAE, KAA, VAV, KAV

Kodiert: 00100, 10100, 00101, 10101, 00100, 10101, 01000, 11000, 01001, 11100, 01100

Transkript 5

Original: KBG, VBG, KBBd, VBBd, KAA

Kodiert: 00000, 10000, 00100, 10100, 01001

Transkript 6

Original: KBBd, VBBd, KBA, VAA, KAA

Kodiert: 00100, 10100, 00101, 11001, 01001

Transkript 7

Original: KBG, VBBd, KBBd, VBA, VAA, KAA, VAV, KAV

Kodiert: 00000, 10100, 00100, 10101, 11001, 01001, 11100, 01100