Search papers, labs, and topics across Lattice.
This paper investigates active learning algorithms for deterministic register automata (DRAs) over both dense and non-dense ordered data domains, presenting a unified framework for the active learning problem. The authors develop a polynomial-time active learning procedure that utilizes oracles for membership, equivalence, and memorability queries, significantly enhancing the efficiency of learning DRAs. Additionally, they establish that the minimization of DRAs over the non-dense ordered domain of integers is decidable, thereby extending existing results and improving complexity bounds for related decision problems.
Active learning for deterministic register automata is now polynomial-time solvable across both dense and non-dense ordered domains, unlocking new possibilities in automata theory.
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.
