Developments of efficient algorithms for learning from examples of formal languages and their applications

我们已经开发了多项式时间算法来检查确定性受限单计数器换能器的等价性，这些换能器是只有一个堆栈符号的确定性下推换能器，通过空栈或最终状态接受。证明了确定性下推自动机的一个子类Szilard严格确定性限制单计数器自动机和一个有限状态换能器(简称FST)的子类严格前缀确定性FST在极限上是多项式时间可从正数据识别的。此外，我们还利用k-可逆语言类的识别算法改进了孟加拉雀鸟歌唱的分析方法，k-可逆语言是正则语言的一个子类。

We have developed polynomial time algorithms for checking the equivalence of deterministic restricted one-counter transducers, which are deterministic pushdown transducers having just one stack symbol, that accept by empty stack or by final state. We have proved that a subclass of deterministic pushdown automata called Szilard strict deterministic restricted one-counter automata and a subclass of finite state transducers(FST's for short)called strict prefix deterministic FST's are polynomial time identifiable in the limit from positive data. Furthermore, we have improved the method for analyzing songs of the Bengalese finch using an identification algorithm for the class of k-reversible languages, which is a subclass of regular languages.