% 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=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{\Huge\textbf{From Scheme to DeepProbLog} \\[2mm]
       \LARGE ARS as a Methodological Blueprint \\[2mm]
       \LARGE for Modern Neuro-Symbolic Programming}

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

\date{\large 1994--2026}

\begin{document}

\maketitle

\begin{abstract}
This paper traces the methodological continuity from early implementations of 
the Algorithmic Recursive Sequence Analysis (ARS) in Scheme, Pascal, and Lisp 
(1992--1994) to contemporary neuro-symbolic programming frameworks such as 
DeepProbLog (2018). I argue that the ARS already embodied the core principles 
of neuro-symbolic integration—pattern recognition (System 1), rule-based 
reasoning (System 2), probabilistic uncertainty quantification, and explainability 
by design—decades before the term "neuro-symbolic AI" was coined. The paper 
first reconstructs the ARS's proto-neuro-symbolic architecture, then introduces 
DeepProbLog as a modern framework that implements similar principles with 
greater scalability, and finally demonstrates a DeepProbLog implementation of 
the classic ARS sales conversation corpus. The synthesis shows that ARS provides 
a methodological blueprint that DeepProbLog can instantiate technically. I 
conclude with a research agenda for integrating ARS's methodological rigor with 
DeepProbLog's computational power.
\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introduction: From Lisp to DeepProbLog}

The Algorithmic Recursive Sequence Analysis (ARS), as documented in the early 
Jupyter notebooks and code files from 1992--1994, represents one of the earliest 
systematic attempts to integrate pattern recognition with rule-based reasoning 
in the analysis of sequential social interactions. The three core implementations—

\begin{itemize}
    \item \textbf{Induktor in Scheme}: Inducing probabilistic context-free 
    grammars (PCFG) from terminal symbol strings through transition counting,
    \item \textbf{Parser in Pascal}: Validating the well-formedness of sequences 
    using a chart parser,
    \item \textbf{Transduktor in Lisp}: Generating new sequences from the 
    induced grammar,
\end{itemize}

—collectively embody what today is called \textbf{neuro-symbolic AI}. They combine 
data-driven pattern discovery (the inductor) with symbolic rule application 
(the parser and transducer), and they quantify uncertainty through probabilistic 
weights.

In the intervening three decades, the field has developed more sophisticated 
frameworks for neuro-symbolic integration. One of the most prominent is 
\textbf{DeepProbLog} \citep{manhaeve2018deepproblog}, which extends the 
probabilistic logic programming language ProbLog with neural predicates learned 
by deep networks. DeepProbLog allows users to define symbolic rules with 
probabilities, while neural networks learn the probabilities of ground facts 
from data.

This paper makes three contributions:

\begin{enumerate}
    \item It reconstructs the ARS architecture as a \textbf{proto-neuro-symbolic} 
    system and maps its components to contemporary neuro-symbolic concepts.
    
    \item It introduces DeepProbLog as a modern framework that implements the 
    same principles with greater scalability and neural integration.
    
    \item It presents a \textbf{DeepProbLog implementation} of the classic ARS 
    sales conversation corpus, demonstrating how the ARS methodology can be 
    ported to a modern neuro-symbolic framework.
\end{enumerate}

The overarching thesis is that \textbf{ARS provides a methodological blueprint 
that DeepProbLog can instantiate technically}. The two approaches are not 
competitors but complements: ARS contributes methodological rigor and 
interpretive grounding; DeepProbLog contributes scalability and neural learning.

\section{The ARS Architecture as Proto-Neuro-Symbolic System}

\subsection{Three Components, Three Cognitive Functions}

The ARS's three implementations can be mapped to the System 1 / System 2 
distinction popularized by Kahneman \citep{kahneman2011thinking} and adopted 
by neuro-symbolic AI research \citep{marcus2020next}:

\begin{table}[H]
\centering
\caption{ARS Components as Cognitive Systems}
\label{tab:cognitive}
\begin{tabular}{@{} p{3cm} p{4cm} p{6cm} @{}}
\toprule
\textbf{Component} & \textbf{Cognitive Function} & \textbf{Neuro-Symbolic Mapping} \\
\midrule
Induktor (Scheme) & Pattern recognition, transition counting & System 1 (learning from data) \\
Parser (Pascal) & Structural validation, well-formedness checking & System 2 (rule application) \\
Transduktor (Lisp) & Generative rule application & System 2 (symbolic generation) \\
Multiagent (Python) & Role assignment, interaction & Hybrid (decision tree + grammar) \\
\bottomrule
\end{tabular}
\end{table}

\subsection{The Probabilistic Grammar as a Neuro-Symbolic Interface}

The induced probabilistic context-free grammar (PCFG) serves as the central 
neuro-symbolic interface:

\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}

Each production rule has a probability (implicitly 1.0 in this simplified 
grammar, but weighted by empirical frequencies in the full implementation). 
The grammar is simultaneously:

\begin{itemize}
    \item \textbf{Symbolic}: Rules are explicit, inspectable, and falsifiable.
    \item \textbf{Probabilistic}: Rule applications have probabilities based 
    on empirical frequencies.
    \item \textbf{Generative}: New sequences can be generated by applying rules.
    \item \textbf{Verifiable}: The parser can check whether a sequence is 
    well-formed.
\end{itemize}

These four properties are exactly what contemporary neuro-symbolic frameworks 
aim to achieve.

\subsection{The Multiagent System as Neuro-Symbolic Prototype}

The Python multiagent system (Zellen 29--33 in the notebook) is particularly 
instructive:

\begin{lstlisting}[caption=Multiagent Role Assignment]
# Entscheidung über die Rollenverteilung basierend auf Ware und Zahlungsmittel
if agent_k_ware > agent_v_ware:
    agent_k_role = 'Käufer'
    agent_v_role = 'Verkäufer'
else:
    agent_k_role = 'Verkäufer'
    agent_v_role = 'Käufer'
\end{lstlisting}

This decision tree is a \textbf{symbolic rule} (System 2) that determines agent 
roles based on a simple pattern (System 1: comparing two numbers). The subsequent 
interaction follows the probabilistic grammar. This is a hybrid architecture: 
the role assignment is deterministic and rule-based; the dialogue generation 
is probabilistic and grammar-based.

The ARS thus anticipates the \textbf{Neural | Symbolic} pattern in Kautz's 
taxonomy \citep{kautz2020third}: neural (or heuristic) perception determines 
symbolic roles; symbolic reasoning (the grammar) governs subsequent behavior.

\section{DeepProbLog: A Modern Neuro-Symbolic Framework}

\subsection{What DeepProbLog Is}

DeepProbLog \citep{manhaeve2018deepproblog} extends the probabilistic logic 
programming language ProbLog with \textbf{neural predicates}. A neural predicate 
is a predicate whose truth probability is computed by a neural network. For 
example, a neural predicate `digit(image, d)` might represent the probability 
that an image shows digit `d`.

DeepProbLog programs consist of:

\begin{itemize}
    \item \textbf{Facts}: Ground atoms with probabilities (e.g., `0.5::edge(a,b)`).
    \item \textbf{Rules}: Logical implications (e.g., `path(X,Y) :- edge(X,Y)`).
    \item \textbf{Neural predicates}: Predicates defined by neural networks.
    \item \textbf{Queries}: Questions to be answered probabilistically.
\end{itemize}

Inference in DeepProbLog computes the probability of a query given the program 
and the neural network outputs. Learning updates the neural network weights to 
maximize the likelihood of observed data.

\subsection{Mapping ARS Concepts to DeepProbLog}

\begin{table}[H]
\centering
\caption{Mapping ARS to DeepProbLog}
\label{tab:mapping}
\begin{tabular}{@{} p{4cm} p{4cm} p{4cm} @{}}
\toprule
\textbf{ARS Concept} & \textbf{DeepProbLog Concept} & \textbf{Explanation} \\
\midrule
Terminal symbols & Ground facts & `KBG`, `VBG`, `KBBd`, etc. \\
Production rules & Logical rules & `next(X,Y) :- transition(X,Y)` \\
Transition probabilities & Fact probabilities & `0.8::next(KBG, VBG)` \\
Induktor (transition counting) & Neural predicate learning & Learned from data \\
Parser (well-formedness) & Proof search & Query `next(KBG, VBG)` \\
Transduktor (generation) & Sampling from distribution & `sample(next(Start, X))` \\
Multiagent roles & Probabilistic decision rules & Role assignment with probability \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Why DeepProbLog Is a Natural Successor to ARS}

DeepProbLog preserves the key methodological virtues of ARS:

\begin{enumerate}
    \item \textbf{Explainability}: Rules are explicit and inspectable.
    \item \textbf{Probabilistic uncertainty}: Probabilities quantify uncertainty.
    \item \textbf{Generative capacity}: New sequences can be generated.
    \item \textbf{Verifiability}: Queries can be checked.
\end{enumerate}

But it adds capabilities that ARS lacks:

\begin{enumerate}
    \item \textbf{Neural integration}: Neural networks can learn probabilities 
    from raw data (images, text, audio), not just from pre-coded categories.
    
    \item \textbf{Scalability}: DeepProbLog can handle large datasets through 
    stochastic gradient descent.
    
    \item \textbf{Continuous learning}: The neural network can be updated 
    incrementally as new data arrives.
    
    \item \textbf{Deep feature learning}: Neural networks can automatically 
    discover relevant features, reducing the need for manual category formation.
\end{enumerate}

\section{DeepProbLog Implementation of the ARS Corpus}

\subsection{The Terminal Symbols as Probabilistic Facts}

The first step is to encode the ARS terminal symbols as probabilistic facts. 
The transition probabilities are learned from the corpus:

\begin{lstlisting}[caption=DeepProbLog Encoding of ARS Grammar]
% DeepProbLog implementation of ARS grammar for sales conversations
% Based on the Aachen market transcript (1994)

% Terminal symbols as predicates
predicate(kbg/0). predicate(vbg/0). predicate(kbbd/0). predicate(vbbd/0).
predicate(kba/0). predicate(vba/0). predicate(kae/0). predicate(vae/0).
predicate(kaa/0). predicate(vaa/0). predicate(kav/0). predicate(vav/0).

% Neural predicates for transition probabilities
nn(transition, [in:symbol, out:symbol]) :: neural_network.

% Rules: well-formed sequences follow transitions
% Start symbol is KBG (customer greeting)
next(S) :- transition(start, S).

% Recursive rule for sequences of length > 1
next([A,B|Rest]) :-
    transition(A, B),
    next([B|Rest]).

% Query: probability that a given sequence is well-formed
query(well_formed(Sequence)) :- next(Sequence).

% Generation: sample a well-formed sequence
sample(well_formed(S)) :- next(S).
\end{lstlisting}

\subsection{Learning Transition Probabilities from Data}

The neural network for transition probabilities can be trained on the terminal 
symbol sequences extracted from the ARS corpus. The corpus is:

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

In DeepProbLog, we can encode this as training data:

\begin{lstlisting}[caption=Training Data Encoding]
% Training examples: observed transitions
train(transition(kbg, vbg), true).
train(transition(vbg, kbbd), true).
train(transition(kbbd, vbbd), true).
train(transition(vbbd, kba), true).
train(transition(kba, vba), true).
train(transition(vba, kbbd), true).
train(transition(vba, kae), true).
train(transition(kae, vae), true).
train(transition(vae, kae), true).
train(transition(vae, kaa), true).
train(transition(kaa, vaa), true).
train(transition(vaa, kav), true).
train(transition(kav, vav), true).

% Negative examples (optional)
train(transition(kbg, kbbd), false).
train(transition(vbg, vbg), false).
\end{lstlisting}

The neural network learns to assign high probabilities to the observed 
transitions and low probabilities to unobserved ones. After training, 
the network approximates the empirical transition frequencies.

\subsection{The Multiagent System in DeepProbLog}

The multiagent system can be implemented as a set of probabilistic rules 
with role assignment:

\begin{lstlisting}[caption=Multiagent System in DeepProbLog]
% Agent roles based on goods and money endowments
% These could be learned by neural networks from data
nn(role, [in:goods, in:money, out:role]) :: role_network.

% Role assignment rule
agent_role(A, buyer) :- goods(A, G), money(A, M), role(G, M, buyer).
agent_role(A, seller) :- goods(A, G), money(A, M), role(G, M, seller).

% Interaction rules based on roles
utterance(A, kb) :- agent_role(A, buyer), start_turn.
utterance(A, vg) :- agent_role(A, seller), previous_utterance(_, kb).

% Grammar-based dialogue continuation
next_utterance(A, Sym) :-
    previous_utterance(_, PrevSym),
    transition(PrevSym, Sym),
    agent_role(A, _).

% Query: probability distribution of next utterance given current state
query(next_utterance(seller, Sym)).
\end{lstlisting}

\subsection{Explainability in DeepProbLog}

A key advantage of DeepProbLog over pure neural networks is \textbf{explainability 
by design}. For any query, DeepProbLog can provide a proof tree:

\begin{lstlisting}[caption=Explainability Output]
| ?- explain(well_formed([KBG, VBG, KBBd, VBBd, KBA])).

Proof:
1. well_formed([KBG, VBG, KBBd, VBBd, KBA])
   ← next([KBG, VBG, KBBd, VBBd, KBA])
2. next([KBG, VBG, KBBd, VBBd, KBA])
   ← transition(KBG, VBG) ∧ next([VBG, KBBd, VBBd, KBA])
3. transition(KBG, VBG) ← neural_network(KBG, VBG) [p = 0.67]
4. next([VBG, KBBd, VBBd, KBA])
   ← transition(VBG, KBBd) ∧ next([KBBd, VBBd, KBA])
5. transition(VBG, KBBd) ← neural_network(VBG, KBBd) [p = 1.00]
   ... (continued)

Probability: 0.67 × 1.00 × 0.67 × ... = 0.42
\end{lstlisting}

This proof tree is directly interpretable and maps precisely to the ARS 
grammar rules. The only difference is that the probabilities are learned 
by a neural network rather than counted manually.

\subsection{Comparison with the Original ARS Implementation}

\begin{table}[H]
\centering
\caption{ARS vs. DeepProbLog Implementation}
\label{tab:comparison}
\begin{tabular}{@{} p{4cm} p{4cm} p{4cm} @{}}
\toprule
\textbf{Criterion} & \textbf{ARS (Scheme/Lisp)} & \textbf{DeepProbLog} \\
\midrule
Probability learning & Manual counting & Neural network learning \\
Rule representation & Association lists & Logical predicates \\
Parsing algorithm & Chart parser (hand-coded) & Proof search (built-in) \\
Generation & Custom transducer & Sampling from distribution \\
Explainability & Traceable via code & Proof trees \\
Scalability & Low (n=8) & High (n > 1000) \\
Neural integration & None & Full (neural predicates) \\
\bottomrule
\end{tabular}
\end{table}

The DeepProbLog implementation preserves the methodological virtues of ARS 
while adding scalability and neural learning. It is not a replacement but 
a \textbf{technical instantiation} of the same methodological principles.

\section{Toward a Synthesis: ARS as Blueprint, DeepProbLog as Engine}

\subsection{What ARS Contributes to DeepProbLog}

The ARS methodology offers three lessons for DeepProbLog practitioners:

\begin{enumerate}
    \item \textbf{Interpretive grounding}: The meaning of symbols must be 
    documented. A DeepProbLog program with uninterpreted symbols is not 
    explanatory. ARS shows how to ground symbols in qualitative interpretation.
    
    \item \textbf{Separation of structure and statistics}: ARS maintains a 
    strict separation between structural rules (deterministic, logical) and 
    statistical regularities (probabilistic, empirical). DeepProbLog's 
    mixture of logical rules and neural probabilities risks conflating these 
    levels. ARS suggests keeping them separate in the program structure.
    
    \item \textbf{Falsifiability as validation}: ARS insists that grammars 
    must be falsifiable by counterexamples. DeepProbLog's validation typically 
    relies on likelihood maximization. ARS suggests supplementing this with 
    qualitative falsification tests.
\end{enumerate}

\subsection{What DeepProbLog Contributes to ARS}

Conversely, DeepProbLog offers three enhancements to ARS practitioners:

\begin{enumerate}
    \item \textbf{Scalable learning}: ARS's manual transition counting does 
    not scale. DeepProbLog's neural learning can handle thousands of examples.
    
    \item \textbf{Raw data integration}: ARS requires pre-coded terminal 
    symbols. DeepProbLog can learn directly from raw data (text, images, 
    audio) through neural predicates.
    
    \item \textbf{Continuous updating}: ARS grammars are static. DeepProbLog 
    networks can be updated incrementally as new data arrives.
\end{enumerate}

\subsection{A Research Agenda for Neuro-Symbolic ARS}

Based on this synthesis, I propose a research agenda:

\begin{enumerate}
    \item \textbf{Port the ARS corpus to DeepProbLog}: Complete the 
    implementation of the sales conversation grammar in DeepProbLog, 
    including all 12 terminal symbols and their transition probabilities.
    
    \item \textbf{Add neural predicates for raw audio/text}: Train neural 
    networks to map raw transcripts directly to terminal symbols, bypassing 
    manual coding.
    
    \item \textbf{Implement the multiagent system}: Build a full multiagent 
    system where agents learn roles and interaction patterns through 
    DeepProbLog.
    
    \item \textbf{Validate with the XAI criteria}: Evaluate the DeepProbLog 
    implementation against the ARS XAI criteria (meaningfulness, accuracy, 
    knowledge limits).
    
    \item \textbf{Scale to larger corpora}: Apply the DeepProbLog ARS to 
    larger datasets (hundreds or thousands of conversations) to test 
    scalability.
\end{enumerate}

\section{Conclusion}

This paper has traced the methodological continuity from early ARS 
implementations in Scheme, Pascal, and Lisp to contemporary neuro-symbolic 
programming in DeepProbLog. I have argued that ARS already embodied the 
core principles of neuro-symbolic integration—pattern recognition, rule-based 
reasoning, probabilistic uncertainty, and explainability by design—decades 
before the term was coined.

The mapping from ARS concepts to DeepProbLog is direct and natural. The 
probabilistic grammar becomes a set of logical rules with neural predicates; 
the parser becomes proof search; the transducer becomes sampling. DeepProbLog 
does not replace ARS but \textit{instantiates} its methodological blueprint 
with modern computational tools.

The synthesis is not a competition but a complement. ARS provides the 
methodological rigor and interpretive grounding that DeepProbLog (and 
neuro-symbolic AI more generally) often lacks. DeepProbLog provides the 
scalability and neural learning that ARS lacks. Together, they point toward 
a \textbf{methodologically grounded, scalable neuro-symbolic framework} for 
the analysis of sequential social interactions.

The question for future research is not whether ARS or DeepProbLog is superior. 
Both are tools for different purposes. The question is how to integrate them 
so that the methodological lessons of ARS inform the technical development 
of DeepProbLog, and the computational power of DeepProbLog extends the reach 
of ARS.

\newpage
\begin{thebibliography}{99}

\bibitem[Kahneman(2011)]{kahneman2011thinking}
Kahneman, D. (2011). \textit{Thinking, Fast and Slow}. Farrar, Straus and Giroux.

\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[Manhaeve et al.(2018)]{manhaeve2018deepproblog}
Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., \& De Raedt, L. (2018). 
DeepProbLog: Neural probabilistic logic programming. \textit{Advances in 
Neural Information Processing Systems}, 31.

\bibitem[Marcus(2020)]{marcus2020next}
Marcus, G. (2020). The next decade in AI: Four steps towards robust artificial 
intelligence. \textit{arXiv preprint arXiv:2002.06177}.

\end{thebibliography}

\end{document}