Title: Inference of Deterministic Finite Automata via Q-Learning Show Chinese title

Title: 通过Q学习推断确定性有限自动机

Abstract: Traditional approaches to inference of deterministic finite-state automata (DFA) stem from symbolic AI, including both active learning methods (e.g., Angluin's L* algorithm and its variants) and passive techniques (e.g., Biermann and Feldman's method, RPNI). Meanwhile, sub-symbolic AI, particularly machine learning, offers alternative paradigms for learning from data, such as supervised, unsupervised, and reinforcement learning (RL). This paper investigates the use of Q-learning, a well-known reinforcement learning algorithm, for the passive inference of deterministic finite automata. It builds on the core insight that the learned Q-function, which maps state-action pairs to rewards, can be reinterpreted as the transition function of a DFA over a finite domain. This provides a novel bridge between sub-symbolic learning and symbolic representations. The paper demonstrates how Q-learning can be adapted for automaton inference and provides an evaluation on several examples. Show Chinese abstract

Abstract: 传统推断确定性有限状态自动机（DFA）的方法源于符号人工智能，包括主动学习方法（例如，Angluin的L*算法及其变体）和被动技术（例如，Biermann和Feldman的方法，RPNI）。 同时，亚符号人工智能，特别是机器学习，为从数据中学习提供了替代范式，如监督学习、无监督学习和强化学习（RL）。 本文研究了Q-learning这一著名的强化学习算法在被动推断确定性有限状态自动机中的应用。 它建立在核心洞察之上，即学习到的Q函数，将状态-动作对映射到奖励，可以重新解释为有限域上的DFA的转移函数。 这为亚符号学习和符号表示之间提供了一种新的桥梁。 本文展示了如何适应Q-learning用于自动机推断，并在几个示例上进行了评估。