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

开发用于从形式语言及其应用的示例中学习的有效算法

• 批准号: 20500007
• 负责人: WAKATSUKI Mitsuo
• 金额: $ 2.91万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500007/
• 关键词: 計算論的学習理論; 正例からの学習; 極限同定; 等価性判定; アルゴリズム; 決定性文脈自由言語; プッシュダウンオートマトン; プッシュダウン変換器; 変換器

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.

我们开发了多项式时间算法来检查确定性受限单计数器传感器的等价性，这是确定性下推传感器只有一个堆栈符号，接受空堆栈或最终状态。我们证明了确定性下推自动机的一个子类称为Szilard严格确定性限制单计数器自动机和有限状态传感器的一个子类称为严格前缀确定性FST在正数据的极限上是多项式时间可识别的。此外，我们使用k-可逆语言类的识别算法改进了分析孟加拉雀鸣声的方法，k-可逆语言是规则语言的一个子类。

项目成果

実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム

实时终态接受型确定性有限单计数器变换器多项式时间等价判定算法

• 发表时间: 2011
• 期刊: 京都大学数理解析研究所講究録
• 作者: 蕪城俊克;他;若月光夫，清野和司，富田悦次，西野哲朗
• 通讯作者: 若月光夫，清野和司，富田悦次，西野哲朗

in "Biomedical Engineering, Trends in Electronics, Communications and Software"(Efficient algorithms for finding maximum and maximal cliques : Effective tools for bioinformatics)

在“生物医学工程，电子、通信和软件趋势”中（寻找最大和最大派系的有效算法：生物信息学的有效工具）

• 发表时间: 2011
• 作者: E.Tomita;T.Akutsu;T.Matsunaga
• 通讯作者: T.Matsunaga

A feasible approach for automatic detection and recognition of the Bengalese finch songnotes and their sequences

一种自动检测和识别孟加拉雀歌曲音符及其序列的可行方法

• 发表时间: 2010
• 期刊: Journal of Intelligent Learning Systems and Applications Vol.2, No.4
• 作者: Khan Md.M.S.;T.Nishino;K.Sasahara;M.Takahashi;K.Okanoya
• 通讯作者: K.Okanoya

空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定アルゴリズム

具有空栈接受公式的确定性有限单计数器转换器多项式时间等价判定算法

• 发表时间: 2010
• 作者: 若月光夫;清野和司;富田悦次;西野哲朗
• 通讯作者: 西野哲朗

A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique

• DOI: 10.1007/978-3-642-11440-3_18
• 发表时间: 2010-02
• 作者: E. Tomita;Yoichi Sutani;Takanori Higashi;Shinya Takahashi;Mitsuo Wakatsuki