一句话：研究符号有限状态自动机（SFA）的可学习性，给出查询学习与极限可识别性的正反条件及规模度量。
本文研究符号有限状态自动机（SFA）的可学习性，SFA 在软件验证中应用广泛。现有查询学习结果均为正面；作者给出其高效可学习的必要条件，得到首个负面结果。重点考察多项式时间与数据下的极限可识别性及强化版高效可识别性，即是否存在系统性的特征样本集使学习器正确推断目标语言。作者给出极限识别的必要条件和高效可学习的充分条件，导出正反结果。由于 SFA 一般无规范形式且迁移谓词复杂度与迁移数存在权衡，文中先定义规模度量，再据此分析相关过程复杂度，并考察规范化 SFA、整齐 SFA 及单调有效布尔代数上的 SFA。本文为 CSL'22 论文扩展版。
We study the learnability of symbolic finite state automata (SFA), a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data, and its strengthening efficient identifiability, which are concerned with the existence of a systematic set of characteristic samples from which a learner can correctly infer the target language. We provide a necessary condition for identification of SFAs in the limit using polynomial time and data, and a sufficient condition for efficient learnability of SFAs. From these conditions we derive a positive and a negative result. The performance of a learning algorithm is typically bounded as a function of the size of the representation of the target language. Since SFAs, in general, do not have a canonical form, and there are trade-offs between the complexity of the predicates on the transitions and the number of transitions, we start by defining size measures for SFAs. We revisit the complexity of procedures on SFAs and analyze them according to these measures, paying attention to the special forms of SFAs: normalized SFAs and neat SFAs, as well as to SFAs over a monotonic effective Boolean algebra. This is an extended version of the paper with the same title published in CSL'22.