统一框架下高效学习有序数据域上的寄存器自动机。
Learning Canonical Register Automata over Ordered Data Domains
- 提出统一算法，用成员、等价和记忆性查询学习有序数据域上的确定性寄存器自动机。
- 首次证明整数域上寄存器自动机可判定最小化，拓展了原有结果。
- 改进相关决策问题的复杂度界，适用于实际学习系统设计。
寄存器自动机是带有记忆的有限自动机，用于识别无限字母表上的数据语言。本文研究在有序数据域（包括稠密域如有理数和非稠密域如整数）上确定性寄存器自动机（DRAs）的主动学习算法。我们证明，稠密与非稠密有序域上的主动学习问题可纳入同一统一框架。具体地，设计并实现了基于成员、等价和记忆性查询的多项式时间主动学习过程。记忆性查询最初用于具有等值测试的域。该统一框架还带来新结论：整数域上DRAs的最小化问题是可判定的，扩展了此前仅在稠密域成立的结果。最后，我们给出了与学习查询密切相关的若干决策问题的更优复杂度界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。