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

Feb 25, 2026

Error-awareness Accelerates Active Automata Learning

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.

Loes Kruger, Sebastian Junges, Jurriaan Rot

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

Automata Learning Active Learning Data-Efficient Learning

Ask PDF

May 8, 2026

SMT-Based Active Learning of Weighted Automata

We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/L*-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.

Tiago Ferreira, Kevin Batz, Alexandra Silva

University College London, London, UK · Cornell University, Ithaca, NY, USA

Active Learning Satisfiability Modulo Theories Automata Learning

Ask PDF

Sep 23, 2026

On the Sample Complexity of Active Learning with Membership Queries

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

Ganghua Wang, Shaddin Dughmi

Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California

Active Learning Statistical Learning Theory

Ask PDF

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