一句话：首次给出多项式时间算法，用成员与等价查询学习一类非平凡的派生 ω-树语言。
本文研究无限树语言的查询学习，旨在获得可学习非平凡 ω-树语言类的多项式时间算法。作者给出通用归约：对任意由确定性 Büchi 接受器识别的 ω-词语言类，将派生 ω-树语言类的学习多项式时间归约到其底层 ω-词语言类的学习。归约使用成员与等价查询，结合 Maler 和 Pnueli 对 weak regular ω-词语言的多项式时间算法，首次实现派生 ω-树语言的多项式时间查询学习。论文还证明，对有限词及 Büchi ω-词接受器，返回反例的 subset query 可由不返回反例的 subset query 多项式时间实现；并指出此前常规 ω-树学习算法有误。
We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of $\omega$-tree languages derived from weak regular $\omega$-word languages in polynomial time. The method is a general polynomial time reduction of learning a class of derived $\omega$-tree languages to learning the underlying class of $\omega$-word languages, for any class of $\omega$-word languages recognized by a deterministic B\"{u}chi acceptor. Our reduction, combined with the polynomial time learning algorithm of Maler and Pnueli [1995] for the class of weak regular $\omega$-word languages yields the main result. We also show that subset queries that return counterexamples can be implemented in polynomial time using subset queries that return no counterexamples for deterministic or non-deterministic finite word acceptors, and deterministic or non-deterministic B\"{u}chi $\omega$-word acceptors. A previous claim of an algorithm to learn regular $\omega$-trees due to Jayasrirani, Begam and Thomas [2008] is unfortunately incorrect, as shown in Angluin [2016].
@article{paperbot764,
title = {Query learning of derived $\omega$-tree languages in polynomial time},
author = {Dana Angluin and Timos Antonopoulos and Dana Fisman},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:21)2019}
}