扩展李氏算法，让机器自动学习带数理条件的有限状态机。
Active Learning of Symbolic Automata Over Rational Numbers
- 用有理数上的逻辑条件替代传统字母表，实现无限输入空间的自动机学习
- 查询次数与状态转移数和谓词复杂度呈线性关系，理论最优
- 适用于实时数据、正则表达式等含数值判断的新场景
自动机学习在人工智能和软件工程中有广泛应用。核心方法是Angluin提出的$ L^* $算法，可在提供最小充分教师的前提下，以多项式时间学习确定性有限状态自动机（DFAs）。然而，$ L^* $仅适用于有限字母表，限制了其应用范围。本文将$ L^* $扩展至可学习使用有理数上谓词的符号自动机，即支持无限且稠密字母表的自动机。该成果使$ L^* $算法能应用于新领域，如真实世界的正则表达式（real RGX）和时间序列分析。此外，所提算法在理论上是最优的：向教师提问次数最多与状态转移数及谓词表示大小呈线性关系。
原文摘要 · Abstract (English)
Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the $L^*$ algorithm, introduced by Angluin. The $L^*$ algorithm learns deterministic finite-state automata (DFAs) in polynomial time when provided with a minimally adequate teacher. Unfortunately, the $L^*$ algorithm can only learn DFAs over finite alphabets, which limits its applicability. In this paper, we extend $L^*$ to learn symbolic automata whose transitions use predicates over rational numbers, i.e., over infinite and dense alphabets. Our result makes the $L^*$ algorithm applicable to new settings like (real) RGX, and time series. Furthermore, our proposed algorithm is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the number of transitions, and to the representation size of the predicates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。