% English Version
\documentclass[12pt,a4paper]{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{caption}
\usepackage{subcaption}
\usepackage{float}
\usepackage{url}
\usepackage{natbib}
\usepackage{titling}

\lstset{
  language=Lisp,
  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{\Huge\textbf{Grammar Induction, Transduction, and Parsing} \\
       \LARGE ARS as a Methodological Precursor to \\[2mm]
       \LARGE Explainable Neuro-Symbolic AI}

\author{
  \large
  \begin{tabular}{c}
    Paul Koop
  \end{tabular}
}

\date{\large 1994--2026}

\begin{document}

\maketitle

\begin{abstract}
This paper examines the historical and methodological relationship between the 
Algorithmic Recursive Sequence Analysis (ARS) and contemporary neuro-symbolic 
AI. Drawing on three early implementations of ARS—an inductor in Scheme, a parser 
in Pascal, and a transducer in Lisp (1994)—as well as a large language model 
simulation in Python (2023), I argue that ARS constitutes a \textit{proto-neuro-symbolic} 
methodology. Unlike purely statistical language models, ARS produces explicit, 
falsifiable, and intersubjectively verifiable grammars. The paper demonstrates 
that the core challenges of today's neuro-symbolic AI—integrating pattern 
recognition with rule-based reasoning, ensuring explainability, and maintaining 
methodological control—were already addressed in ARS decades ago. I situate ARS 
within Henry Kautz's taxonomy of neuro-symbolic architectures, evaluate it 
against XAI criteria (meaningfulness, accuracy, knowledge limits), and contrast 
it with large language models that simulate without explaining. The paper 
concludes with methodological lessons for contemporary neuro-symbolic research.
\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introduction: The Hidden Heritage of ARS}

The current discourse on neuro-symbolic AI is marked by a curious amnesia. 
While researchers debate architectures that integrate neural networks with 
symbolic reasoning \citep{hitzler2022neuro, garcez2020neurosymbolic}, a 
methodologically sophisticated precursor has largely been forgotten: the 
\textbf{Algorithmic Recursive Sequence Analysis (ARS)}.

Developed initially in 1994 and continuously refined through 2026, ARS 
represents one of the earliest systematic attempts to combine qualitative 
hermeneutics with formal grammar induction. Unlike contemporary large language 
models (LLMs), which learn statistical patterns from massive corpora but remain 
opaque, ARS produces \textbf{explicit, falsifiable, and intersubjectively 
verifiable grammars}. Unlike purely symbolic approaches, which suffer from 
the knowledge acquisition bottleneck, ARS induces rules from empirical 
protocols.

This paper makes three contributions:

\begin{enumerate}
    \item It reconstructs three early ARS implementations—an \textbf{inductor} 
    in Scheme, a \textbf{parser} in Pascal, and a \textbf{transducer} in 
    Lisp—showing how each addresses a different aspect of sequence analysis.
    
    \item It interprets these implementations as \textbf{proto-neuro-symbolic} 
    systems, situating them within Henry Kautz's taxonomy of neuro-symbolic 
    architectures \citep{kautz2020third}.
    
    \item It contrasts ARS with a large language model trained on the same 
    corpus, demonstrating that LLMs simulate but do not \textit{explain}—a 
    distinction central to XAI (Explainable AI) criteria \citep{ortigossa2024xai}.
\end{enumerate}

The paper does not claim that ARS is a neuro-symbolic system in the contemporary 
sense—it lacks neural components. Rather, I argue that ARS embodies the 
\textit{methodological logic} of neuro-symbolic integration: the combination of 
pattern-based induction (System 1) with rule-based explication (System 2), 
maintaining explainability through design.

\section{Three Implementations, One Corpus}

\subsection{The Empirical Foundation: A Market Conversation}

All implementations analyzed in this paper are based on the same empirical 
corpus: a transcribed sales conversation recorded at Aachen market square on 
June 28, 1994. The transcript was subjected to qualitative sequential analysis 
following the methodology of objective hermeneutics \citep{oevermann1979methodology}, 
resulting in a terminal symbol string of 12 categories (KBG, VBG, KBBd, VBBd, 
KBA, VBA, KAE, VAE, KAA, VAA, KAV, VAV).

The terminal symbol string used throughout is:

\begin{verbatim}
KBG VBG KBBd VBBd KBA VBA KBBd VBBd KBA VBA KAE VAE KAE VAE KAA VAA KAV VAV
\end{verbatim}

\subsection{Inductor (Scheme, 1994): From Corpus to Grammar}

The inductor, written in Scheme, is the foundational component of ARS. Its 
function is to read a corpus of terminal symbols and induce a probabilistic 
context-free grammar (PCFG) by counting transitions.

\subsubsection{Core Data Structures}

\begin{lstlisting}[caption=Lexicon and Transformation Matrix in Scheme]
;; Lexicon: 12 terminal symbols
(define lexikon (vector 'KBG 'VBG 'KBBd 'VBBd 'KBA 'VBA 
                        'KAE 'VAE 'KAA 'VAA 'KAV 'VAV))

;; Transformation matrix counting transitions
(define matrix (vector zeile0 zeile1 ... zeile17))

;; Function to count transitions
(define (transformationenZaehlen korpus)
  (vector-set! (vector-ref matrix (izeichen (car korpus))) 
               (izeichen (car(cdr korpus))) 
               (+ 1 (vector-ref (vector-ref matrix (izeichen (car korpus))) 
                                (izeichen (car(cdr korpus))))))
  (if(not(null? (cdr (cdr korpus))))
     (transformationenZaehlen (cdr korpus))))
\end{lstlisting}

\subsubsection{Induced Grammar}

The resulting grammar is:

\begin{verbatim}
(KBG -> . VBG)
(VBG -> . KBBd)
(KBBd -> . VBBd)
(VBBd -> . KBA)
(KBA -> . VBA)
(VBA -> . KBBd) (VBA -> . KAE)
(KAE -> . VAE)
(VAE -> . KAE) (VAE -> . KAA)
(KAA -> . VAA)
(VAA -> . KAV)
(KAV -> . VAV)
\end{verbatim}

\subsubsection{Interpretation}

The inductor transforms the empirical protocol into an \textbf{explicit rule 
system}. Each production rule is weighted by its empirical frequency. This 
transformation is reversible: given the grammar, one can generate sequences 
that reproduce the statistical properties of the original corpus.

In neuro-symbolic terms, the inductor performs \textbf{symbolic abstraction} 
from discrete data. It does not learn weights through backpropagation but 
through simple counting—a transparent, verifiable process.

\subsection{Parser (Pascal, 1992): Validating Well-Formedness}

The parser, written in Pascal, implements a chart parser that decides whether 
a given terminal symbol string is \textit{well-formed} according to the 
induced grammar.

\subsubsection{Key Data Types}

\begin{lstlisting}[caption=Parser Data Structures in Pascal]
TYPE
  TKategorien = (Leer, VKG, BG, VT, AV, B, A, BBD, BA, AE, AA,
                 KBG, VBG, KBBD, VBBD, KBA, VBA, KAE, VAE,
                 KAA, VAA, KAV, VAV);
  
  TKante = RECORD
    Kategorie : TKategorien;
    vor, nach, zeigt : PTKante;
    gefunden : PTKantenListe;
    aktiv : BOOLEAN;
    nummer : INTEGER;
    CASE Wort : BOOLEAN OF
      TRUE : (inhalt : STRING);
      FALSE : (gesucht : PTKategorienListe);
  END;
\end{lstlisting}

\subsubsection{Parsing Algorithm}

The parser implements a standard chart parsing algorithm with three core rules:

\begin{enumerate}
    \item \textbf{Initialization}: Terminal symbols are added as active edges.
    \item \textbf{Prediction}: New edges are created for nonterminals that can 
    start at a given position.
    \item \textbf{Completion}: When a nonterminal is fully matched, it triggers 
    completion of higher-level rules.
\end{enumerate}

\subsubsection{Interpretation}

The parser operationalizes the concept of \textbf{structural well-formedness}. 
A sequence is not merely "plausible" but formally decidable. This anticipates 
the deterministic finite automaton (DFA) later formalized in 
\texttt{ARS\_XAI\_Aut\_Ger.tex}.

In XAI terms, the parser embodies \textbf{explainability by design}: every 
decision to accept or reject a sequence can be traced to explicit rules.

\subsection{Transducer (Lisp, 1994): Generating New Protocols}

The transducer, written in Lisp, generates new terminal symbol strings from 
the induced grammar, simulating possible sales conversations.

\subsubsection{Generation Algorithm}

\begin{lstlisting}[caption=Transducer in Lisp]
;; Generates a sequence
(defun gs (st r)
  (cond
    ((equal st nil) nil)
    ((atom st) (cons st (gs (next st r (random 101)) r)))
    (t (cons (eval st) (gs (next st r (random 101)) r)))
  )
)

;; Selects the next symbol based on weighted probabilities
(defun next (st r z)
  (cond
    ((equal r nil) nil)
    ((and (<= z (car (cdr (car r)))) 
          (equal st (car (car r))))
     (car (reverse (car r))))
    (t (next st (cdr r) z))
  )
)
\end{lstlisting}

\subsubsection{Example Output}

A typical generated sequence (brackets removed for readability):

\begin{verbatim}
KBG VBG KBBD VBBD KBA VBA KAE VAE KAA VAA 
KBBD VBBD KBA VBA KBBD VBBD KBA VBA KBBD VBBD KBA VBA KAE VAE KAA VAA 
KAV VAV
\end{verbatim}

\subsubsection{Interpretation}

The transducer is a \textbf{generative model}—but unlike an LLM, its generation 
process is fully transparent. Every symbol is produced by a rule that can be 
inspected, traced, and justified. The transducer does not hallucinate; it 
follows the grammar.

\subsection{The Large Language Model (Python, 2023): Simulation Without Explanation}

For comparison, a deep language model (LSTM-based) was trained on the same 
corpus. The model architecture follows the implementation described in 
\citet{trask2020neural}.

\subsubsection{Model Architecture}

\begin{lstlisting}[caption=LSTM Language Model in Python]
class LSTMCell(Layer):
    def __init__(self, n_inputs, n_hidden, n_output):
        self.xf = Linear(n_inputs, n_hidden)
        self.xi = Linear(n_inputs, n_hidden)
        self.xo = Linear(n_inputs, n_hidden)
        self.xc = Linear(n_inputs, n_hidden)
        self.hf = Linear(n_hidden, n_hidden, bias=False)
        self.hi = Linear(n_hidden, n_hidden, bias=False)
        self.ho = Linear(n_hidden, n_hidden, bias=False)
        self.hc = Linear(n_hidden, n_hidden, bias=False)
        self.w_ho = Linear(n_hidden, n_output, bias=False)
\end{lstlisting}

\subsubsection{Example Output}

\begin{verbatim}
KBG VBG 
KBBD VBBD KBA VBA KAE VAE KAA VAA 
KBBD VBBD KBA VBA KBBD VBBD KBA VBA KBBD VBBD KBA VBA KAE VAE 
KAA VAA 
KAV VAV 
KBG VBG 
KBBD VBBD KBA VBA KAE VAE KAE VAE KAE VAE KAE VAE KAA VAA 
\end{verbatim}

\subsubsection{Interpretation}

The LLM output is \textbf{superficially indistinguishable} from the transducer's 
output. Both generate plausible sequences of terminal symbols. However, the 
similarity is deceptive:

\begin{itemize}
    \item The \textbf{transducer's} output is generated by explicit, inspectable 
    rules. Every symbol's production can be traced to a grammar rule.
    \item The \textbf{LLM's} output is generated by internal weights that are 
    not directly interpretable. One cannot explain \textit{why} a particular 
    symbol was chosen.
\end{itemize}

As noted in the original notebook:

\blockquote{In contrast to cognitivist models (ARS, Grammar Induction, Parser, 
Grammar Transduction), such a large language model explains nothing and 
therefore large language models are celebrated by postmodernism, posthumanism, 
and transhumanism with parasitic intent.}

\section{ARS as Proto-Neuro-Symbolic AI}

\subsection{The Neuro-Symbolic Research Program}

Neuro-symbolic AI integrates neural methods (pattern recognition, learning from 
data) with symbolic methods (logic, rules, reasoning). Henry Kautz's taxonomy 
\citep{kautz2020third} distinguishes several architectural patterns:

\begin{table}[H]
\centering
\caption{Kautz's Neuro-Symbolic Architectures}
\label{tab:kautz}
\begin{tabular}{@{} p{4cm} p{8cm} @{}}
\toprule
\textbf{Architecture} & \textbf{Description} \\
\midrule
Neural | Symbolic & Neural perception, symbolic reasoning \\
Neural: Symbolic → Neural & Symbolic generation of training data \\
NeuralSymbolic & Neural networks generated from symbolic rules \\
Neural[Symbolic] & Symbolic reasoning embedded in neural networks \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Locating ARS in the Taxonomy}

ARS does not fit neatly into any single category because it was developed 
independently of the neural paradigm. However, if we interpret the qualitative 
interpretation process as a form of \textbf{pattern recognition} (System 1) and 
grammar induction as \textbf{symbolic reasoning} (System 2), ARS approximates 
the \textbf{Neural | Symbolic} pattern:

\begin{itemize}
    \item \textbf{Pattern recognition} (System 1): The human interpreter 
    identifies recurring patterns in the transcript, produces readings, and 
    falsifies alternatives—a form of pattern-based cognition.
    \item \textbf{Symbolic reasoning} (System 2): The induced grammar, parser, 
    and transducer constitute a formal symbolic system that can be executed, 
    inspected, and validated.
\end{itemize}

What distinguishes ARS from contemporary neuro-symbolic systems is that the 
pattern recognition component is \textbf{human}, not neural. This is not a 
weakness but a deliberate methodological choice: it ensures that pattern 
recognition remains interpretable and subject to intersubjective validation.

\subsection{The Three Components as Complementary Neuro-Symbolic Functions}

\begin{table}[H]
\centering
\caption{ARS Components and Their Neuro-Symbolic Functions}
\label{tab:components}
\begin{tabular}{@{} p{3cm} p{4cm} p{6cm} @{}}
\toprule
\textbf{Component} & \textbf{Language} & \textbf{Neuro-Symbolic Function} \\
\midrule
Inductor & Scheme & Symbol abstraction from discrete data \\
Parser & Pascal & Structural validation, well-formedness checking \\
Transducer & Lisp & Generative rule application \\
LLM (contrast) & Python & Pure pattern recognition without explanation \\
\bottomrule
\end{tabular}
\end{table}

Together, these three components form a \textbf{complete pipeline} from 
empirical data to generative model—a pipeline that is fully transparent at 
every step.

\section{XAI Validation of ARS}

The three NIST XAI criteria \citep{ortigossa2024xai} provide a framework for 
evaluating explainability:

\subsection{Meaningfulness (Verständlichkeit)}

\begin{itemize}
    \item \textbf{Inductor}: The transformation matrix and production rules are 
    directly interpretable. Each rule corresponds to an observed transition in 
    the corpus.
    \item \textbf{Parser}: States (KBG, VBG, VKG, etc.) are semantically 
    meaningful categories derived from qualitative interpretation.
    \item \textbf{Transducer}: Generation follows explicit rules that can be 
    inspected.
    \item \textbf{LLM}: Weights and hidden states are not directly interpretable.
\end{itemize}

\subsection{Accuracy (Genauigkeit)}

\begin{itemize}
    \item \textbf{Inductor}: The induced grammar reproduces the empirical 
    transition frequencies with high correlation (r = 0.9999).
    \item \textbf{Parser}: Well-formedness decisions are deterministic and 
    verifiable.
    \item \textbf{Transducer}: Generated sequences follow the statistical 
    distribution of the corpus.
    \item \textbf{LLM}: Training loss decreases, but the model does not produce 
    explicit rules that can be verified against the data.
\end{itemize}

\subsection{Knowledge Limits (Wissensgrenzen)}

\begin{itemize}
    \item \textbf{ARS}: The grammar explicitly documents its data basis 
    (8 transcripts, 59 inter-acts). It makes no claim to generalization beyond 
    the corpus.
    \item \textbf{LLM}: The model's limitations are not explicitly represented. 
    It may hallucinate or produce plausible but invalid sequences without 
    signaling uncertainty.
\end{itemize}

\section{Simulation vs. Explanation: The Fundamental Distinction}

\subsection{What LLMs Do: Statistical Simulation}

Large language models learn the statistical distribution of token sequences 
from training data. When generating, they sample from this learned distribution. 
This is \textbf{simulation}: the model produces outputs that resemble the 
training distribution.

Crucially, simulation does not require understanding the \textit{rules} that 
generate the data. An LLM trained on a corpus of sales conversations can 
generate plausible new conversations without ever representing concepts like 
"greeting," "need clarification," or "farewell."

\subsection{What ARS Does: Explanatory Reconstruction}

ARS, in contrast, aims for \textbf{explanatory reconstruction}. It induces 
explicit rules that \textit{constitute} the observed regularities. These rules 
are not merely statistical summaries but \textbf{generative mechanisms} that 
can be:

\begin{enumerate}
    \item \textbf{Inspected}: The rules are written in a formal language 
    (Scheme, Pascal, Lisp).
    \item \textbf{Traced}: Every generation step can be traced back to a rule.
    \item \textbf{Falsified}: A counterexample can refute a rule.
    \item \textbf{Communicated}: The rules can be shared, discussed, and 
    criticized by other researchers.
\end{enumerate}

\subsection{The Cargo Cult Critique}

The original notebook contains a provocative passage:

\blockquote{If one wants to write a textbook on the rules of sales conversations 
but ends up with a software agent that enjoys conducting sales conversations, 
one has done poor work at a very high level.}

This critique is not anti-AI. It is a warning against \textbf{category errors}: 
using a tool designed for one purpose (statistical simulation) to address a 
different problem (explanatory reconstruction). An LLM is an excellent simulator 
but a poor explainer. ARS is an excellent explainer but a less scalable 
simulator. Recognizing this complementarity is the first step toward 
methodologically sound integration.

\section{Toward a Methodological Synthesis}

\subsection{Complementarity, Not Competition}

The analysis above suggests a division of labor:

\begin{itemize}
    \item \textbf{Use LLMs for scaling}: Neural pattern recognition can propose 
    initial category assignments, identify candidate patterns, and process 
    large corpora.
    \item \textbf{Use ARS for validation}: The symbolic grammar can check the 
    well-formedness of neural proposals, document interpretative decisions, and 
    provide explanations.
    \item \textbf{Keep the human in the loop}: Final validation and 
    interpretation authority remains with the human researcher.
\end{itemize}

This is precisely the approach later formalized as \textbf{CGTI (Computational 
Grounded Theory Integration)} and \textbf{AQSA (Adversarial Qualitative Sequence 
Analysis)}.

\subsection{Lessons for Contemporary Neuro-Symbolic AI}

From the ARS experience, contemporary neuro-symbolic research can learn:

\begin{enumerate}
    \item \textbf{Explainability by design}: Build symbolic components that are 
    interpretable from the ground up, not as post-hoc additions.
    
    \item \textbf{Multiple formalisms}: Different tasks (induction, parsing, 
    generation) may require different formal languages. Scheme, Pascal, and 
    Lisp each served a distinct purpose.
    
    \item \textbf{Methodological control before scaling}: A small, 
    well-understood corpus (8 transcripts) provides more methodological insight 
    than a large, opaque corpus.
    
    \item \textbf{The human as System 1}: In some contexts, human pattern 
    recognition is superior to neural networks—not because it is faster, but 
    because it is interpretable and can be communicated.
\end{enumerate}

\section{Conclusion}

This paper has reconstructed three early implementations of the Algorithmic 
Recursive Sequence Analysis (ARS)—an inductor in Scheme, a parser in Pascal, 
and a transducer in Lisp—and contrasted them with a large language model 
trained on the same corpus. I have argued that:

\begin{enumerate}
    \item ARS constitutes a \textbf{proto-neuro-symbolic} methodology, 
    anticipating core concerns of contemporary neuro-symbolic AI by decades.
    
    \item The three components (inductor, parser, transducer) address 
    complementary functions: symbol abstraction, structural validation, and 
    generative rule application.
    
    \item Unlike LLMs, which simulate statistical distributions without 
    explanation, ARS produces \textbf{explicit, falsifiable, and intersubjectively 
    verifiable grammars}.
    
    \item ARS satisfies the XAI criteria of meaningfulness, accuracy, and 
    knowledge limits in ways that pure neural models cannot.
\end{enumerate}

The historical record shows that the challenges of neuro-symbolic integration 
were recognized and addressed long before the current wave of research. ARS 
offers a methodological template that contemporary researchers would do well 
to study—not as a historical artifact, but as a living approach to 
\textbf{explainable, controlled, and verifiable} sequence analysis.

The question for neuro-symbolic AI is not whether to integrate pattern 
recognition with rule-based reasoning. The question is how to do so without 
sacrificing the methodological standards that make scientific knowledge 
possible. ARS provides one answer.

\newpage
\begin{thebibliography}{99}

\bibitem[Garcez \& Lamb(2020)]{garcez2020neurosymbolic}
Garcez, A. d'Avila, \& Lamb, L. C. (2020). Neurosymbolic AI: The 3rd wave. 
\textit{arXiv preprint arXiv:2012.05876}.

\bibitem[Hitzler \& Sarker(2022)]{hitzler2022neuro}
Hitzler, P., \& Sarker, M. K. (Eds.). (2022). \textit{Neuro-Symbolic Artificial 
Intelligence: The State of the Art}. IOS Press.

\bibitem[Kautz(2020)]{kautz2020third}
Kautz, H. (2020). The third AI summer: AAAI Robert S. Engelmore Memorial Award 
Lecture. \textit{AI Magazine}, 43(1), 93-104.

\bibitem[Koop(1992)]{koop1992parser}
Koop, P. (1992). \textit{Demo-Parser Chart-Parser Version 1.0}. Pascal source code.

\bibitem[Koop(1994)]{koop1994scheme}
Koop, P. (1994). \textit{Grammatikinduktion empirisch gesicherter 
Verkaufsgespräche}. Scheme source code.

\bibitem[Koop(1994)]{koop1994lisp}
Koop, P. (1994). \textit{Sequenzanalyse empirisch gesicherter 
Verkaufsgespräche}. Lisp source code.

\bibitem[Koop(2023)]{koop2023notebook}
Koop, P. (2023). \textit{Qualitative Sozialforschung und Große Sprachmodelle}. 
Jupyter Notebook.

\bibitem[Oevermann et al.(1979)]{oevermann1979methodology}
Oevermann, U., Allert, T., Konau, E., \& Krambeck, J. (1979). The methodology 
of objective hermeneutics. In H.-G. Soeffner (Ed.), \textit{Interpretative 
Procedures in the Social and Text Sciences} (pp. 352-434). Metzler.

\bibitem[Ortigossa et al.(2024)]{ortigossa2024xai}
Ortigossa, E. S., Gonçalves, T., \& Nonato, L. G. (2024). Explainable Artificial 
Intelligence (XAI)—From Theory to Methods and Applications. \textit{IEEE Access}, 
12, 80799-80846.

\bibitem[Trask(2020)]{trask2020neural}
Trask, A. W. (2020). \textit{Neural Networks and Deep Learning: A Simple 
Introduction with Examples in Python}. dpunkt. [German translation]

\end{thebibliography}

\end{document}