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

我们已经开发了多项式时间算法检查确定性限制一计数器换能器，这是确定性的下推换能器只有一个堆栈符号，接受空堆栈或最终状态的等效性。我们证明了一个子类的确定性下推自动机称为Szilard严格确定性限制一计数器自动机和一个子类的有限状态转换器（FST的简称）称为严格前缀确定性FST的是多项式时间可识别的限制，从积极的数据。此外，我们已经改进了用于分析孟加拉雀的歌曲的方法，使用识别算法的类的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.