[2604.02244] (PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version)

Computer Science > Formal Languages and Automata Theory arXiv:2604.02244 (cs) [Submitted on 2 Apr 2026] Title:(PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version) Authors:Robert Baumgartner, Sicco Verwer View a PDF of the paper titled (PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version), by Robert Baumgartner and Sicco Verwer View PDF HTML (experimental) 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 is now a full Section. State machines 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 i...