一句话：提出 residual nominal automata 子类，证明其规范表示可由有限观察构造，从而支持主动学习。
本文研究哪些数据语言存在主动学习算法，这一问题在作者先前工作中仍未解决，且对非确定性自动机识别的语言尤为困难。作者引入 residual nominal automata——非确定性名义自动机的一个子类，并证明该类具有规范代表，且总能通过有限次观察构造出来。尽管 residuality 对名义自动机是不可判定的语义性质，这一构造仍为主动学习算法提供了基础。其核心是基于 residual languages 的机器无关特征化，并为此发展了名义格理论中的新结果。该工作被视为理解具有某种非确定性的自动机可学习性的重要一步。
We are motivated by the following question: which data languages admit an active learning algorithm? This question was left open in previous work by the authors, and is particularly challenging for languages recognised by nondeterministic automata. To answer it, we develop the theory of residual nominal automata, a subclass of nondeterministic nominal automata. We prove that this class has canonical representatives, which can always be constructed via a finite number of observations. This property enables active learning algorithms, and makes up for the fact that residuality -- a semantic property -- is undecidable for nominal automata. Our construction for canonical residual automata is based on a machine-independent characterisation of residual languages, for which we develop new results in nominal lattice theory. Studying residuality in the context of nominal languages is a step towards a better understanding of learnability of automata with some sort of nondeterminism.
@article{paperbot1729,
title = {Residuality and Learning for Nondeterministic Nominal Automata},
author = {Joshua Moerman and Matteo Sammartino},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:29)2022}
}