Learning Canonical Register Automata over Ordered Data Domains

Yong Li; Qiyi Tang; Di-De Yen

cs.CLAug 19, 2026

Learning Canonical Register Automata over Ordered Data Domains

Authors: Yong Li, Qiyi Tang, Di-De Yen

Organizations: Key Laboratory of System Software (Chinese Academy of Sciences), Beijing, China · Institute of Software, Chinese Academy of Sciences, Beijing, China · School of Computer Science and Informatics, University of Liverpool, UK

Abstract

Register automata are finite automata equipped with memory that recognize data languages over infinite alphabets. In this work, we investigate active learning algorithms for deterministic register automata (DRAs) over ordered data domains--covering both dense domains, such as the rationals, and non-dense domains such as the integers. We show that the active learning problem for DRAs over both dense and non-dense ordered domains can be treated within a single unified framework. More specifically, we develop and implement a polynomial-time active learning procedure for DRAs over ordered domains, using oracles for membership, equivalence and memorability queries. The memorability queries were originally introduced for learning DRAs over domains with identity tests. Our unified framework also leads to a new consequence: minimization of DRAs over the non-dense ordered domain of integers is decidable, extending a result previously known only for dense domains. Finally, we give improved complexity bounds of several decision problems for DRAs over ordered domains that are closely related to the queries used in active learning.

Figures & tables

Figure 1: A well-typed DRA

\mathcal{A}_{\textit{mid}}

recognizing

L_{\textit{mid}}

where sink state and its related transitions are omitted.

Figure 2: The example DRA

\mathcal{A}

where the missing transitions are labeled with

*

, and the observation table

\mathcal{T}

where the extension set

X

are omitted.

Figure 3: Unclosed table

\mathcal{T}_{0}

, closed table

\mathcal{T}_{1}

and its induced DRAs

\mathcal{H}_{1}

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Closed Table

\mathcal{T}_{2}

and its derived DRA

\mathcal{H}_{2}

Panel of Figure 5 — Figure 5: The x-axis is the the length of word $n=1,\ldots,25$ for $L_{n}$ . Left: the number of EQ s and Mem s for each $n$ . Right: the number of MQ s.

Model	Input DRA size		Learned DRA size		# $\textsf{TQ}/\textsf{MQ}$		# EQ		$\textsf{TQ}/\textsf{MQ}$ Time (s)		EQ Time (s)		Our Mem
Model	RaLib	Ours	RaLib	Ours	RaLib	Ours	RaLib	Ours	RaLib	Ours	RaLib	Ours	# Mem	Time
$L_{2}$	9	4	8	4	34	39	2	2	$<$ 1	$<$ 1	2.19	$<$ 1	6	$<$ 1
$L_{3}$	16	6	10	6	49	156	2	4	$<$ 1	$<$ 1	2.57	$<$ 1	12	$<$ 1
$L_{4}$	22	8	12	8	68	662	2	8	$<$ 1	$<$ 1	2.91	$<$ 1	18	$<$ 1
$L_{5}$	28	10	14	10	91	2,173	2	14	$<$ 1	$<$ 1	3.07	$<$ 1	24	$<$ 1
$L_{6}$	34	12	16	12	118	5,885	2	22	$<$ 1	$<$ 1	3.37	$<$ 1	30	$<$ 1

Appendix

Table 1: Experimental results for RaLib and our approach on

L_{n}

. DRA sizes are reported as numbers of states, and runtimes are given in seconds. All runtimes are total operation times.

$n$	States	Transitions	EQ	MQ	Mem	MQ time (s)	Total Time (s)
$1$	$3$	$3$	$2$	$24$	$3$	<1	<1
$2$	$4$	$6$	$2$	$39$	$6$	<1	<1
$3$	$6$	$12$	$4$	$156$	$12$	<1	<1
$4$	$8$	$18$	$8$	$662$	$18$	<1	<1
$5$	$10$	$24$	$14$	$2173$	$24$	<1	<1
$6$	$12$	$30$	$22$	$5885$	$30$	<1	<1

Appendix

Table 7

	$M$	$\varepsilon$	$0\cdot 1\cdot 0.5$
$\varepsilon$	$\varepsilon$	$-$	$+$
$0$	$0$	$-$	$-$
$0\cdot 1$	$0\cdot 1$	$-$	$-$
$0\cdot 1\cdot 0.5$	$\varepsilon$	$+$	$-$
$0\cdot-1$	$\varepsilon$	$-$	$-$

Appendix

Table 8

Figure 6: Learned DRA recognizing $L_{\textit{mid}}$

Panel of Figure 7 — Figure 7: Average statistics for learning random minimal well-typed DRAs.

Size	Avg # Transitions	Avg # EQ	Avg # MQ	Avg # Mem	Avg Time (s)
5	$12.2$	$2.3$	$75.0$	$12.2$	$0.12$
10	$34.6$	$4.4$	$593.1$	$34.6$	$0.28$
15	$57.4$	$6.8$	$2086.1$	$57.4$	$1.08$
20	$82.9$	$9.2$	$5131.1$	$82.9$	$2.02$
25	$105.8$	$11.9$	$10\,542.2$	$105.8$	$2.84$
30	$130.5$	$13.8$	$17\,883.5$	$130.5$	$5.33$

Appendix

Table 11

Automata Learning

See all 15 papers

Error-awareness Accelerates Active Automata Learning
Feb 25, 2026Loes Kruger, Sebastian Junges, Jurriaan RotAutomata Learning Active Learning
Institute for Computing and Information Sciences, Radboud University, Nijmegen, the Netherlands
SMT-Based Active Learning of Weighted Automata
May 8, 2026Tiago Ferreira, Kevin Batz, Alexandra SilvaActive Learning Satisfiability Modulo Theories
University College London, London, UK · Cornell University, Ithaca, NY, USA
On the Sample Complexity of Active Learning with Membership Queries
Sep 23, 2026Ganghua Wang, Shaddin DughmiActive Learning Statistical Learning Theory
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California

Feb 25, 2026J/K move · Enter open · S save

Error-awareness Accelerates Active Automata Learning

Loes Kruger, Sebastian Junges, Jurriaan Rot

Institute for Computing and Information Sciences, Radboud University, Nijmegen, the Netherlands

Automata Learning Active Learning Data-Efficient Learning

Open paper AskPDF arXiv

Active automata learning (AAL) algorithms can learn a behavioral model of a system from interacting with it. The primary challenge remains scaling to larger models, in particular in the presence of many possible inputs to the system. Modern AAL algorithms fail to scale even if, in every state, most inputs lead to errors. In various challenging problems from the literature, these errors are observable, i.e., they emit a known error output. Motivated by these problems, we study learning these systems more efficiently. Further, we consider various degrees of knowledge about which inputs are non-error producing at which state. For each level of knowledge, we provide a matching adaptation of the state-of-the-art AAL algorithm L# to make the most of this domain knowledge. Our empirical evaluation demonstrates that the methods accelerate learning by orders of magnitude with strong but realistic domain knowledge to a single order of magnitude with limited domain knowledge.

Abstract

Automata Learning

Explore similar work

Error-awareness Accelerates Active Automata Learning

SMT-Based Active Learning of Weighted Automata

On the Sample Complexity of Active Learning with Membership Queries