We define the problem of learning a transducer ${S}$ from a target language $U$ containing possibly conflicting transducers, using membership queries and conjecture queries. The requirement is that the language of ${S}$ be a subset of $U$. We argue that this is a natural question in many situations in hardware and software verification. We devise a learning algorithm for this problem and show that its time and query complexity is polynomial with respect to the rank of the target language, its incompatibility measure, and the maximal length of a given counterexample. We report on experiments conducted with a prototype implementation.
翻译：我们定义了从目标语言中学习一个含有可能相互冲突的传送者、使用成员查询和猜测询问的美元的目标语言来学习一个以美元为单位的传送者的问题,要求以美元为单位的语言是美元的一个子项。我们争辩说,在硬件和软件核查的许多情况下,这是一个自然的问题。我们为这一问题设计了一种学习算法,并表明,在目标语言的级别、不兼容性计量标准以及一个特定反例的最大长度方面,它的时间和查询的复杂性是多方面的。我们报告了以原型实施进行的实验。
相关内容
微信扫码咨询专知VIP会员