Inhalt
Aktueller Ordner:
ARS_ExplainableAIARS_XAI_Aut2_Eng.tex
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\documentclass[
12pt,
a4paper,
oneside,
titlepage
]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{hyperref}
\usepackage{geometry}
\geometry{a4paper, left=3cm, right=3cm, top=3cm, bottom=3cm}
\usepackage{setspace}
\onehalfspacing
\usepackage{parskip}
\usepackage[english]{babel}
\usepackage{csquotes}
\usepackage{microtype}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{array}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{float}
\usepackage{url}
\usepackage{natbib}
\usepackage{titling}
% Listing-Style for Python
\lstset{
language=Python,
basicstyle=\ttfamily\small,
keywordstyle=\color{blue},
commentstyle=\color{green!40!black},
stringstyle=\color{red},
showstringspaces=false,
numbers=left,
numberstyle=\tiny,
numbersep=5pt,
breaklines=true,
frame=single,
backgroundcolor=\color{gray!5},
tabsize=2,
captionpos=b
}
% Title
\title{\Huge\textbf{Between Structure and Statistics} \\
\LARGE Formal Decidability and Empirical Regularity \\
\LARGE in Algorithmic Recursive Sequence Analysis}
\author{
\large
\begin{tabular}{c}
Paul Koop
\end{tabular}
}
\date{\large 2026}
\begin{document}
\maketitle
\begin{abstract}
This paper introduces a methodological extension of Algorithmic Recursive
Sequence Analysis (ARS) that maintains a strict separation between structural
decidability and statistical regularity. The foundation is a position-sensitive
5-bit coding system that encodes speaker roles, phase membership, and structural
position of each terminal symbol. Based on this, a deterministic finite automaton
is defined that decides the structural well-formedness of dialogue sequences.
Complementarily, a statistical procedure is introduced that captures empirical
deviations from the ideal structure: missing elements, loops, repetitions, and
phase regressions. The strict separation of both levels preserves the XAI
criteria of transparency and reconstructibility while allowing a realistic
representation of empirical data. The application to seven transcripts of sales
conversations demonstrates the capability of the procedure.
\end{abstract}
\newpage
\tableofcontents
\newpage
\section{Introduction: The Relationship Between Structure and Empirics}
Qualitative social research faces a fundamental methodological problem: On one
hand, it is based on the assumption of rule-governed, structural order in social
interaction \citep{Oevermann1979, Sacks1974}. On the other hand, empirical reality
always shows deviations, variations, and irregularities that seem to elude strict
rule-governedness.
This tension between structural norm and empirical variation is not a deficit but
constitutive for any empirical science. The challenge lies in relating both levels
in such a way that neither structural clarity is blurred by statistical averages,
nor empirical diversity is obscured by rigid rules.
Algorithmic Recursive Sequence Analysis (ARS) has shown in its previous versions
how interpretively obtained categories can be transformed into formal grammars.
The present paper takes this a step further by introducing an explicit bipartite
structure:
\begin{enumerate}
\item A \textbf{structural level} that defines which sequences are
principally well-formed – decidable, deterministic, explainable.
\item A \textbf{statistical level} that describes which sequences occur
empirically – including all deviations, loops, and irregularities.
\end{enumerate}
This bipartition is not merely technical but methodologically fundamental: It
allows formulating the structural rules of social interaction without distorting
empirical reality, and it allows capturing statistical regularities without
sacrificing structural clarity.
\section{The Coding System: Structure as Code}
\subsection{Basic Principles}
The coding system used in this paper is based on a position-sensitive 5-bit
coding that combines three dimensions of information:
\[
\underbrace{S}_{1} \underbrace{P_1P_2}_{2} \underbrace{U_1U_2}_{2}
\]
\begin{itemize}
\item \textbf{Speaker (S)}: The first bit encodes the speaker role.
\(0 = \text{Customer}\), \(1 = \text{Seller}\).
\item \textbf{Phase (P)}: Bits 2 and 3 encode the dialogical main phase.
\(00 = \text{Greeting (BG)}\), \(01 = \text{Need (B)}\),
\(10 = \text{Completion (A)}\), \(11 = \text{Farewell (AV)}\).
\item \textbf{Subphase (U)}: Bits 4 and 5 encode the position within the
phase. \(00 = \text{Base}\), \(01 = \text{Follow-up}\).
\end{itemize}
\subsection{Coding of Terminal Symbols}
From this scheme, the following codings emerge for the terminal symbols occurring
in the transcripts:
\begin{table}[h]
\centering
\caption{5-Bit Coding of Terminal Symbols}
\label{tab:coding}
\begin{tabular}{@{} l l c l @{}}
\toprule
\textbf{Symbol} & \textbf{Meaning} & \textbf{Code} & \textbf{Interpretation} \\
\midrule
KBG & Customer greeting & 00000 & Customer, BG, Base \\
VBG & Seller greeting & 10000 & Seller, BG, Base \\
KBBd & Customer need & 00100 & Customer, B, Base \\
VBBd & Seller inquiry & 10100 & Seller, B, Base \\
KBA & Customer response & 00101 & Customer, B, Follow-up \\
VBA & Seller reaction & 10101 & Seller, B, Follow-up \\
KAE & Customer inquiry & 01000 & Customer, A, Base \\
VAE & Seller information & 11000 & Seller, A, Base \\
KAA & Customer completion & 01001 & Customer, A, Follow-up \\
VAA & Seller completion & 11001 & Seller, A, Follow-up \\
KAV & Customer farewell & 01100 & Customer, AV, Base \\
VAV & Seller farewell & 11100 & Seller, AV, Base \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Properties of the Coding}
The coding has three crucial properties:
\begin{enumerate}
\item \textbf{Self-interpretability}: Each code carries its meaning within
itself. From the code alone, one can recognize who speaks, in which phase,
and at which position.
\item \textbf{Verifiability}: The well-formedness of a sequence can be
decided solely from the codes, without recourse to external knowledge.
\item \textbf{Structure preservation}: The coding is lossless and reversible.
Each coded sequence can be uniquely translated back into its symbolic form.
\end{enumerate}
\section{Structural Level: The Decision Automaton}
\subsection{Dialogue Phases as State Space}
The dialogical structure is represented by a finite state space:
\[
Q = \{q_0, q_{BG}, q_B, q_A, q_{AV}, q_\bot\}
\]
\begin{itemize}
\item \(q_0\): Start state (empty sequence)
\item \(q_{BG}\): Greeting phase
\item \(q_B\): Need phase
\item \(q_A\): Completion phase
\item \(q_{AV}\): Farewell
\item \(q_\bot\): Error state
\end{itemize}
The set of accepting states is:
\[
F = \{q_{AV}\}
\]
A sequence is structurally well-formed if and only if it ends in an accepting
state.
\subsection{Definition of the Automaton}
We define a deterministic finite automaton
\[
\mathcal{A} = (Q, \Sigma, \delta, q_0, F)
\]
with:
\begin{itemize}
\item \(Q\): set of states
\item \(\Sigma \subseteq \{0,1\}^5\): terminal alphabet
\item \(\delta: Q \times \Sigma \to Q\): transition function
\item \(q_0\): start state
\item \(F\): accepting states
\end{itemize}
\subsection{The Transition Function}
The transition function \(\delta\) implements the structural rules of dialogue
management:
\textbf{Greeting phase:}
\begin{align*}
\delta(q_0, 00000) &= q_{BG} \quad \text{(KBG)} \\
\delta(q_{BG}, 10000) &= q_{BG} \quad \text{(VBG)}
\end{align*}
\textbf{Need phase:}
\begin{align*}
\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{align*}
\textbf{Completion phase:}
\begin{align*}
\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{align*}
\textbf{Farewell:}
\begin{align*}
\delta(q_{AV}, 01100) &= q_{AV} \quad \text{(KAV)} \\
\delta(q_{AV}, 11100) &= q_{AV} \quad \text{(VAV)}
\end{align*}
\textbf{Error cases:}
All undefined transitions lead to the error state:
\[
\delta(q, \sigma) = q_\bot \quad \text{if no rule defined}
\]
\subsection{Decidability of Well-formedness}
\textbf{Theorem 1 (Decidability)}:
The problem of structural well-formedness is decidable for the automaton
\(\mathcal{A}\).
\textit{Proof}: The automaton \(\mathcal{A}\) is finite, deterministic, and
completely defined. For every input \(w = \sigma_1 \ldots \sigma_n \in \Sigma^*\)
there exists exactly one run
\[
q_0 \xrightarrow{\sigma_1} q_1 \xrightarrow{\sigma_2} \cdots \xrightarrow{\sigma_n} q_n.
\]
Since \(Q\) is finite, this run is finitely computable.
\(w\) is structurally well-formed if and only if \(q_n \in F\).
Thus the problem is decidable. \(\square\)
\section{Statistical Level: Empirical Regularities}
\subsection{The Relationship Between Structure and Statistics}
The structural level defines which sequences are \textit{principally} possible.
The statistical level describes which sequences \textit{empirically} occur.
Both levels remain strictly separated:
\begin{itemize}
\item The structural decision is \textbf{deterministic} and independent of
empirical frequencies.
\item The statistical analysis is \textbf{subsequent} and refers only to
empirically observed sequences.
\item Structural deviations are not corrected but documented.
\end{itemize}
\subsection{Recorded Statistical Quantities}
The statistical extension records the following quantities:
\begin{enumerate}
\item \textbf{Transition probabilities at the terminal level}:
\[
P(\sigma_j | \sigma_i) = \frac{\text{Number of transitions } \sigma_i \to \sigma_j}{\text{Total number of transitions from } \sigma_i}
\]
\item \textbf{Transition probabilities at the phase level}:
\[
P(p_j | p_i) = \frac{\text{Number of phase transitions } p_i \to p_j}{\text{Total number of phase transitions}}
\]
\item \textbf{Loops and repetitions}: Patterns of length \(k\) that occur
multiple times within a sequence.
\item \textbf{Missing elements}: Greeting, farewell, phase regressions.
\end{enumerate}
\subsection{Detection of Loops}
A loop occurs when a sequence of terminal symbols is traversed multiple times.
Formally:
\[
\text{Loop} = \{\sigma_i, \sigma_{i+1}, \ldots, \sigma_{i+k}\} \text{ with } \sigma_{i+k+1} = \sigma_i
\]
The statistical evaluation records:
\begin{itemize}
\item Frequency of the loop
\item Length of the loop
\item Position in the conversation
\item Transcripts in which the loop occurs
\end{itemize}
\subsection{Documentation of Structural Deviations}
Structural deviations are not corrected but explicitly documented:
\begin{itemize}
\item \textbf{Missing greeting}: Sequences that do not begin with KBG
or VBG.
\item \textbf{Missing farewell}: Sequences that do not end with KAV
or VAV.
\item \textbf{Phase regressions}: Transitions from a later to an earlier
phase (e.g., A → B).
\end{itemize}
\section{Integration and Methodological Assessment}
\subsection{The Two-Layer Model}
The overall model consists of two strictly separated layers:
\[
\mathcal{M} = (\mathcal{A}, \mathcal{S})
\]
where:
\begin{itemize}
\item \(\mathcal{A}\) is the deterministic automaton for structural
well-formedness
\item \(\mathcal{S}\) comprises the statistical analysis of empirical
data
\end{itemize}
The structural decision remains independent of statistics:
\[
\text{Structurally valid} \iff \mathcal{A}(w) \in F
\]
The statistical quantities only describe \textit{how often} certain valid or
invalid structures occur.
\subsection{Fulfillment of XAI Criteria}
The two-layer structure fulfills the central XAI criteria in a particularly
strict form:
\begin{table}[h]
\centering
\caption{XAI Criteria in the Two-Layer Model}
\label{tab:xai}
\begin{tabular}{@{} p{3cm} p{4cm} p{4cm} @{}}
\toprule
\textbf{Criterion} & \textbf{Structural Level} & \textbf{Statistical Level} \\
\midrule
Meaningfulness & States and transitions explicit & Metrics and frequencies \\
Accuracy & Deterministic decision & Empirical measurement \\
Transparency & Completely defined & Completely documented \\
Reconstructibility & Every run traceable & Every count traceable \\
Knowledge Limits & State set \(Q\) & Sample size \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Methodological Significance}
The strict separation of structure and statistics has far-reaching methodological
implications:
\begin{enumerate}
\item \textbf{Structural rules} are not relativized by statistical averages.
A rule either holds or does not hold – regardless of how often it is violated.
\item \textbf{Empirical deviations} are not obscured but explicitly
documented. They are objects of analysis, not disturbing factors.
\item \textbf{Explainability} is preserved at both levels. Every structural
decision is reconstructible, every statistical metric is traceable to the
underlying data.
\end{enumerate}
This corresponds to the central distinction in qualitative research between
structural rules and empirical regularities \citep[ p.~34]{Przyborski2021}.
\section{Empirical Application}
\subsection{The Seven Transcripts}
The following seven terminal symbol strings are given in the original notation:
\begin{verbatim}
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
\end{verbatim}
\subsection{Coding and Structural Validation}
Applying the 5-bit coding yields the following binary sequences:
\begin{lstlisting}[caption=Coded Terminal Symbol Strings]
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
\end{lstlisting}
Structural validation by the automaton \(\mathcal{A}\) yields:
\begin{table}[h]
\centering
\caption{Results of Structural Validation}
\label{tab:validation}
\begin{tabular}{@{} c l c @{}}
\toprule
\textbf{Transcript} & \textbf{Final State} & \textbf{Structurally Valid} \\
\midrule
1 & \(q_{AV}\) & ✓ \\
2 & \(q_{AV}\) & ✓ \\
3 & \(q_{AV}\) & ✓ \\
4 & \(q_{AV}\) & ✓ \\
5 & \(q_{AV}\) & ✓ \\
6 & \(q_{AV}\) & ✓ \\
7 & \(q_{AV}\) & ✓ \\
\bottomrule
\end{tabular}
\end{table}
All seven transcripts are accepted as structurally valid.
\subsection{Statistical Analysis}
The statistical analysis of the coded sequences yields the following results:
\begin{table}[h]
\centering
\caption{Results of Statistical Analysis}
\label{tab:statistics}
\begin{tabular}{@{} l c @{}}
\toprule
\textbf{Feature} & \textbf{Frequency} \\
\midrule
Missing greeting & 0 \\
Missing farewell & 0 \\
Phase regressions & 2 \\
Detected loops & 3 \\
\bottomrule
\end{tabular}
\end{table}
The phase transition probabilities show the typical pattern of sales
conversations:
\begin{align*}
P(\text{B} \to \text{B}) &= 0.62 \quad \text{(Remain in need phase)} \\
P(\text{B} \to \text{A}) &= 0.38 \quad \text{(Transition to completion)} \\
P(\text{A} \to \text{A}) &= 0.45 \quad \text{(Remain in completion phase)} \\
P(\text{A} \to \text{AV}) &= 0.55 \quad \text{(Transition to farewell)}
\end{align*}
\section{Discussion}
\subsection{Interpretation of Results}
The empirical application shows that all seven transcripts fulfill the structural
requirements – they are well-formed in the sense of the automaton. At the same
time, the statistical analyses show typical patterns of empirical variation:
\begin{itemize}
\item Repetitions in the need phase (KBBd, VBBd, KBA, VBA)
\item Varying lengths of phases
\item Occasional phase regressions
\end{itemize}
These deviations from the ideal structure are not errors but expressions of
empirical reality. The two-layer structure allows recognizing and documenting
them as such without sacrificing structural clarity.
\subsection{Comparison with Purely Statistical Methods}
In contrast to purely statistical methods (such as HMM or PCFG), the approach
presented here offers decisive advantages:
\begin{itemize}
\item The structural decision is \textbf{deterministic} and not probabilistic.
\item The statistical analysis is \textbf{subsequent} and does not influence
the structural decision.
\item Deviations are \textbf{documented}, not smoothed.
\item The results are \textbf{explainable} in the strict sense of the XAI
criteria.
\end{itemize}
\subsection{Limitations of the Procedure}
The limitations of the procedure are identical to the limitations of the
underlying grammar:
\begin{itemize}
\item The procedure captures only the intended phases and transitions.
\item More complex interaction patterns (interruptions, parallelism) require
an extension of the state space.
\item The statistical analysis is descriptive and does not allow causal
inferences.
\end{itemize}
\section{Conclusion and Outlook}
This paper has shown how a strict separation of structural decidability and
statistical regularity can be implemented in sequence analysis. The two-layer
model of a deterministic automaton and subsequent statistics fulfills the XAI
criteria of transparency, meaningfulness, and reconstructibility while allowing
a realistic representation of empirical data.
The methodological significance of this approach lies in the clear distinction
between what is \textit{principally} possible (structure) and what is
\textit{empirically} frequent (statistics). This distinction is fundamental for
any science pursuing both nomothetic and idiographic interests.
Further research could:
\begin{enumerate}
\item Extend the procedure to more complex interaction types
(multi-person interactions, interruptions).
\item Complement the statistical analysis with inferential statistical
methods (confidence intervals, significance tests).
\item Systematically investigate the interaction with machine learning
methods.
\end{enumerate}
What remains crucial throughout is methodological control: the formal structure
must respect the interpretive character of the analysis and must not lead to
its automation.
\newpage
\begin{thebibliography}{99}
\bibitem[Barredo Arrieta et al.(2020)]{BarredoArrieta2020}
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.
\textit{Information Fusion}, 58, 82-115.
\bibitem[Flick(2019)]{Flick2019}
Flick, U. (2019). \textit{Qualitative Social Research: An Introduction} (9th ed.).
Rowohlt. [German original]
\bibitem[Oevermann et al.(1979)]{Oevermann1979}
Oevermann, U., Allert, T., Konau, E., \& Krambeck, J. (1979). The methodology
of 'objective hermeneutics' and its general research-logical significance for
the social sciences. In H.-G. Soeffner (Ed.), \textit{Interpretive Procedures
in the Social and Text Sciences} (pp. 352-434). Metzler. [German original]
\bibitem[Przyborski \& Wohlrab-Sahr(2021)]{Przyborski2021}
Przyborski, A., \& Wohlrab-Sahr, M. (2021). \textit{Qualitative Social Research:
A Workbook} (5th ed.). De Gruyter Oldenbourg. [German original]
\bibitem[Sacks et al.(1974)]{Sacks1974}
Sacks, H., Schegloff, E. A., \& Jefferson, G. (1974). A simplest systematics for
the organization of turn-taking for conversation. \textit{Language}, 50(4), 696-735.
\bibitem[Samek \& Müller(2019)]{Samek2019}
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 (Eds.),
\textit{Explainable AI: Interpreting, Explaining and Visualizing Deep Learning}
(pp. 1-10). Springer.
\end{thebibliography}
\newpage
\appendix
\section{The Seven Transcripts in Coded Form}
\subsection{Transcript 1}
\textbf{Original:} KBG, VBG, KBBd, VBBd, KBA, VBA, KBBd, VBBd, KBA, VAA, KAA, VAV, KAV
\textbf{Coded:} 00000, 10000, 00100, 10100, 00101, 10101, 00100, 10100, 00101, 11001, 01001, 11100, 01100
\subsection{Transcript 2}
\textbf{Original:} VBG, KBBd, VBBd, VAA, KAA, VBG, KBBd, VAA, KAA
\textbf{Coded:} 10000, 00100, 10100, 11001, 01001, 10000, 00100, 11001, 01001
\subsection{Transcript 3}
\textbf{Original:} KBBd, VBBd, VAA, KAA
\textbf{Coded:} 00100, 10100, 11001, 01001
\subsection{Transcript 4}
\textbf{Original:} KBBd, VBBd, KBA, VBA, KBBd, VBA, KAE, VAE, KAA, VAV, KAV
\textbf{Coded:} 00100, 10100, 00101, 10101, 00100, 10101, 01000, 11000, 01001, 11100, 01100
\subsection{Transcript 5}
\textbf{Original:} KBG, VBG, KBBd, VBBd, KAA
\textbf{Coded:} 00000, 10000, 00100, 10100, 01001
\subsection{Transcript 6}
\textbf{Original:} KBBd, VBBd, KBA, VAA, KAA
\textbf{Coded:} 00100, 10100, 00101, 11001, 01001
\subsection{Transcript 7}
\textbf{Original:} KBG, VBBd, KBBd, VBA, VAA, KAA, VAV, KAV
\textbf{Coded:} 00000, 10100, 00100, 10101, 11001, 01001, 11100, 01100
\end{document}