一意標準形文法をもつ文脈自由言語族およびその学習に関する研究

具有独特标准语法的上下文无关语系及其学习研究

• 批准号: 18K11150
• 负责人: 吉仲 亮
• 金额: $ 2.83万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11150/
• 关键词: 文法推論; 計算論的学習理論; 無限アルファベット; 文脈自由文法; 有限状態オートマトン; オートマトン; 文脈自由言語; 分布学習; 正則言語

本研究課題は，近年の文脈自由言語に対する分布学習アプローチを発展させ，分布学習可能で一意標準形を持つ文脈自由言語族を探究することを目的としている．2022年度の成果の第一は，無限アルファベット上の文脈自由言語の学習に関するものである．古典的な有限アルファベット上の正則言語の学習手法を，シンボリックオートマトンと呼ばれる言語受理機械を用いて無限アルファベット上の正則言語の学習へと拡張した先行研究を参考にしつつ，正例から極限同定可能であることが知られていた可代入文脈自由言語を無限アルファベット上のそれへと拡張した際の学習可能性について考察した．その結果，文脈自由文法中の規則に現れる無限アルファベット上の概念クラスが学習可能であるだけでは不十分であるという否定的な結果を得る一方で，効率的な学習可能性を損なわない条件を発見し，正例から極限同定可能な無限アルファベット上の文脈自由言語族を見出す，世界初の結果となった．第二の成果は，分布学習アプローチ自体の一般化についてである．従来の文脈自由言語の分布学習では，いかなる文字列と文脈の結合が学習対象の言語に属する文字列を形成するか，という文字列と文脈の関係に焦点を当て，有限個の文脈が受理するような文字列で特徴づけ可能な非終端記号を学習するアプローチをとっていた．本研究ではこれを一般化し，文脈の受理する文字列集合に対するブール演算やスター演算を許した場合に，従来のアプローチでは学習できなかった多様な文脈自由言語が，所属性質問と正例から極限同定可能になることを示した．これらの成果は現在国際会議に投稿中で，査読を待っている状況である．

This research topic aims to explore the development of distributed learning of context-free speech in recent years. The first achievement of 2022 is to explore the development of distributed learning of context-free speech. Classical speech learning techniques on the basis of limited speech, speech processing machinery, speech processing machinery, speech processing machinery For example, the limit of the same fixed possibility can be substituted into the context of free speech can be unlimited. Contextually-free grammar rules are presented in infinite numbers, the concept of learning is possible, the result of negation is obtained, the possibility of learning is effective, the condition of learning is lost, the positive example is limited, the possibility of learning is infinite, the contextually-free speech family is presented, the result of the world is initial. The second achievement is the generalization of distributed learning. The distribution of free speech in context is studied. The combination of text string and context forms the language belonging to the learning object. The focus of text string and context relationship is appropriate. The limited context can be accepted. The character of text string may not be the terminal sign. In this study, we generalize the context of the text set to the context of the calculation of the case, the context of the learning of the case to the context of the free speech, the nature of the case to the limit of the same possible. The results of the conference are now being submitted to international conferences, and the status of the conference is being examined.

项目成果

Sorting Balls and Water: Equivalence and Computational Complexity

• DOI: 10.4230/lipics.fun.2022.16
• 发表时间: 2022-02
• 期刊: Theor. Comput. Sci.
• 作者: Takehiro Ito;J. Kawahara;S. Minato;Y. Otachi;Toshiki Saitoh;Akira Suzuki;Ryuhei Uehara;T. Uno;Katsuhisa Yamanaka;Ryo Yoshinaka

A Hierarchy of Context-Free Languages Learnable from Positive Data and Membership Queries

可从正数据和成员查询中学习的上下文无关语言的层次结构

• 发表时间: 2021
• 期刊: Proceedings of Machine Learning Research
• 作者: 宮下令央;末石智大;田畑智志;早川智彦;石川正俊;Makoto Kanazawa and Ryo Yoshinaka
• 通讯作者: Makoto Kanazawa and Ryo Yoshinaka

Inside-Outside Algorithm for Macro Grammars

宏语法的内部-外部算法

• 发表时间: 2021
• 作者: Ryuta Kambe;Naoki Kobayashi;Ryosuke Sato;Ayumi Shinohara;Ryo Yoshinaka
• 通讯作者: Ryo Yoshinaka

Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

参数化 DAWG：高效构造和双向模式搜索

• DOI: 10.1016/j.tcs.2022.09.008
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Katsuhito Nakashima;Noriki Fujisato;Diptarama Hendrian;Yuto Nakashima;Ryo Yoshinaka;Shunsuke Inenaga;Hideo Bannai;Ayumi Shinohara;Masayuki Takeda
• 通讯作者: Masayuki Takeda

Grammar Compression with Probabilistic Context-Free Grammar

使用概率上下文无关语法进行语法压缩

• 发表时间: 2020
• 作者: Hiroaki Naganuma;Diptarama Hendrian;Ryo Yoshinaka;Ayumi Shinohara;Naoki Kobayashi
• 通讯作者: Naoki Kobayashi