论文标题
确定性自下而上的名义树自动机的主动学习
Active Learning for Deterministic Bottom-up Nominal Tree Automata
论文作者
论文摘要
名义集在有限自动机的群体理论扩展中起着至无限数据值集的群体理论扩展的核心作用。 Moerman等。提出了一种具有相等对称性的名义单词自动机的主动学习算法。在本文中，我们介绍了确定性的自下而上的名义树自动机（DBNTA），该树在其节点上用轨道有限标称集的元素标记的树上工作。然后，我们证明了DBNTA认可的语言类的Myhill-nerode定理，并为DBNTA提出了一种主动学习算法。该算法可以处理任何支持最少支持的数据对称性，而不仅限于平等对称性和/或总顺序对称性。为了证明该算法的终止，我们在名义集上定义了部分顺序，并表明在任何两个轨道有限集之间的该部分顺序都没有无限的轨道有限标称集。
Nominal set plays a central role in a group-theoretic extension of finite automata to those over an infinite set of data values. Moerman et al. proposed an active learning algorithm for nominal word automata with the equality symmetry. In this paper, we introduce deterministic bottom-up nominal tree automata (DBNTA), which operate on trees whose nodes are labelled with elements of an orbit finite nominal set. We then prove a Myhill-Nerode theorem for the class of languages recognized by DBNTA and propose an active learning algorithm for DBNTA. The algorithm can deal with any data symmetry that admits least support, not restricted to the equality symmetry and/or the total order symmetry. To prove the termination of the algorithm, we define a partial order on nominal sets and show that there is no infinite chain of orbit finite nominal sets with respect to this partial order between any two orbit finite sets.
