PAC learning PDFA from data streams

Robert Baumgartner; Sicco Verwer

cs.FLApr 2, 2026

PAC learning PDFA from data streams

Authors: Robert Baumgartner, Sicco Verwer

Organizations: Department of Software Technology, Delft University of Technology, Delft, The Netherlands

Abstract

This is an extended version of our publication Learning state machines from data streams: A generic strategy and an improved heuristic, International Conference on Grammatical Inference (ICGI) 2023, Rabat, Morocco. It has been extended with a formal proof on PAC-bounds, and the discussion and analysis of a similar approach has been moved from the appendix and now has a full dedicated section. State machine models are models that simulate the behavior of discrete event systems, capable of representing systems such as software systems, network interactions, and control systems, and have been researched extensively. The nature of most learning algorithms however is the assumption that all data be available at the beginning of the algorithm, and little research has been done in learning state machines from streaming data. In this paper, we want to close this gap further by presenting a generic method for learning state machines from data streams, as well as a merge heuristic that uses sketches to account for incomplete prefix trees. We implement our approach in an open-source state merging library and compare it with existing methods. We show the effectiveness of our approach with respect to run-time, memory consumption, and quality of results on a well known open dataset. Additionally, we provide a formal analysis of our algorithm, showing that it is capable of learning within the PAC framework, and show a theoretical improvement to increase run-time, without sacrificing correctness of the algorithm in larger sample sizes.

Figures & tables

Panel of Figure 1 — Figure 1: The two solutions to the problem of uniform distributions in the sketches.

Heuristic	$F==0$	$F==1$	$F==2$	$F==3$	$F==4$
Alergia	1m45s	1m55s	2m8s	2m24s	-
CSS	-	2m1s	2m15s	2m14s	2m50s
CSS-MinHash	-	-	-	3m14s	3m40s
SpaceSave	-	4m37s	6m51s	-	-

Table 1: Runtime comparisons of the heuristics and different future length parameters

F

F

being a placeholder for either

k

F_{s}

, or

L

. Empty fields do not exist or are not interesting to us.

Panel of Figure 2 — Figure 2: Boxplots of all heuristics. Due to the difference in magitude in between the SpaceSave heuristic and the other heuristics we separated them into two sub-plots.

Parameter	$L==1$	$L==2$
$\epsilon$	$0.005$	$0.005$
$\delta$	$0.05$	$0.05$
$\mu$	$0.6$	$0.4$
$K$ (number of prefixes to track)	$20$	$20$
$r$ (number of bootstrapped sketches)	$10$	$10$

Table 2: Hyperparameters used for the SpaceSave heuristic. The parameter’s meaning can be taken from ( Balle et al., 2012 ) .

Strategy	Prob. 1	Prob. 5	Prob. 11	Prob. 18	Prob. 23	Prob. 34	Prob. 45
Batch	250MB	56MB	1.1GB	3.1GB	1.0GB	2.4GB	257MB
Stream old	15MB	13MB	34MB	123MB	63MB	53MB	13MB
Stream new	14MB	13MB	29MB	123MB	63MB	44MB	13MB

Table 3: Memory-footprints compared on a few selected problems. Heuristic employed: CSS-MinHash

F_{s}==4

Figure 3: The function $f(m_{0})$ with varying $\mu$ and $\alpha$ .

Automata Learning

See all 15 papers

Warm Starting State-Space Models with Automata Learning
Mar 5, 2026William Fishell, Sam Nicholas Kouteili, Mark SantolucitoAutomata Learning State Space Models
Columbia University · Yale University · Barnard College, Columbia University
Decoupling Inference from State Updates in Low-Latency Feature Engines via Probabilistic Thinning
Jun 15, 2026Augusto Peres, Iker Perez, Pedro Valdeira +4Efficient Inference
Feedzai
Efficient Learning of Deep State Space Models via Importance Smoothing
May 20, 2026John-Joseph Brady, Nikolas Nusken, Yunpeng LiVariational Inference State Space Models
Centre for Oral, Clinical and Translational Sciences, King’s College London, London, United Kingdom · Department of Mathematics, King’s College London, London, United Kingdom

Mar 5, 2026J/K move · Enter open · S save

Warm Starting State-Space Models with Automata Learning

William Fishell, Sam Nicholas Kouteili, Mark Santolucito

Columbia University · Yale University · Barnard College, Columbia University

Automata Learning State Space Models Neurosymbolic Learning

Open paper AskPDF arXiv

We prove that Moore machines can be exactly realized as state-space models (SSMs), establishing a formal correspondence between symbolic automata and these continuous machine learning architectures. These Moore-SSMs preserve both the complete symbolic structure and input-output behavior of the original Moore machine, but operate in Euclidean space. With this correspondence, we compare the training of SSMs with both passive and active automata learning. In recovering automata from the SYNTCOMP benchmark, we show that SSMs require orders of magnitude more data than symbolic methods and fail to learn state structure. This suggests that symbolic structure provides a strong inductive bias for learning these systems. We leverage this insight to combine the strengths of both automata learning and SSMs in order to learn complex systems efficiently. We learn an adaptive arbitration policy on a suite of arbiters from SYNTCOMP and show that initializing SSMs with symbolically-learned approximations learn both faster and better. We see 2-5 times faster convergence compared to randomly initialized models and better overall model accuracies on test data. Our work lifts automata learning out of purely discrete spaces, enabling principled exploitation of symbolic structure in continuous domains for efficiently learning in complex settings.

Abstract

Automata Learning

Explore similar work

Warm Starting State-Space Models with Automata Learning

Decoupling Inference from State Updates in Low-Latency Feature Engines via Probabilistic Thinning

Efficient Learning of Deep State Space Models via Importance Smoothing