決定性文脈自由言語の部分族に対する学習アルゴリズムの開発とその応用に関する研究

确定性上下文无关语言子群学习算法开发及应用研究

• 批准号: 06780243
• 负责人: 若月 光夫
• 金额: $ 0.38万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780243/
• 关键词: 形式言語理論; 決定性プッシュダウンオートマン; 決定性1カウンタオートマン; 決定性文脈自由言語; 包含性判定; 正則性判定; 計算論的学習理論; 正の例からの極限同定

本研究では,決定性文脈自由言語を受理する決定性プッシュダウンオートマン(DPDA)の構造にある妥当な制約を課した部分族を対象として,計算論的学習理論のパラダイムに基づく帰納推論アルゴリズムを開発することを目的としている。その基礎構築のため,対象の言語族を特徴づける諸性質を明らかにし,その族に対する決定問題を解く効率的な判定アルゴリズムを開発することも研究対象である。まず,DPDAのスタック記号をただ1種類に限定した決定性カウンタ(DROCA)と呼ぶ部分族を対象とし,次の結果を得た。DROCAの受理方式の違いによる言語族間の関係および各言語族の閉包性を明らかにした。続いて,空スタック受理式および実時間最終状態受理式DROCAに対する多項式時間包含性判定アルゴリズムをそれぞれ提案した(前者は1995年電子情報通信学会英文論文誌E-D分冊掲載予定。後者は同論文誌投稿中)。この結果を利用することで,これらDROCAに対する正則性判定が多項式時間で可能であることも明らかにした。これらは,DROCAの上位の族で,DPDAのスタックを底の1記号を除いてただ1種類に限定した決定性1カウンタオートマンに対して,包含性判定が非可解であること,指数オーダの時間量の正則性判定アルゴリズムが提案されているだけであることに比べ対照的な結果である。更に,学習アルゴリズムについては次の結果を得た。実時間空スタック受理式DROCAに各入力記号に対し推移規則を高々1つに限定する等の制約を課した部分族に対する正の例からの極限同定アルゴリズムを開発した。これは,入力記号数を定数とみなせば多項式時間で同定可能である。また,接尾辞決定性正則言語と名付けた正則言語の真部分族に対する正の例からの多項式時間極限同定アルゴリズムを開発した。

This study aims to investigate the structure of deterministic context-free speech (DPDA) and its implications for computation-theoretic learning theory. The basic structure of the speech characteristics of the object is clearly defined, and the decision of the family is made. DPDA's signature is divided into 1 category and 2 categories. The definition of DPDA's signature is divided into 1 category and 2 categories. Droca's processing method is not only the relationship between speech families, but also the closure of speech families. In this paper, we propose a new method for determining the time inclusion of polynomials.(The former is given in E-D of Electronic Information and Communication Society, 1995.) The latter is the same as the paper submission). The result is that the regularity of Droca is determined by polynomial time. In contrast, in the upper family of DROCA,DPDA's character is divided into 1 symbol at the bottom, 1 type is limited, 1 category is decisive, 1 category is inclusive, 1 category is non-solvable, 2 category is included, 3 category is included, and 3 category is included. In addition, learning is not easy to achieve. Time is empty, acceptance formula DROCA is open to all entry marks, transition rules, restrictions, etc. The number of force symbols is fixed. The polynomial time is fixed. A polynomial time limit for a real part of a regular speech is determined.

项目成果

Ken Higuchi,Etsuji Tomita and Mitsuo Wakatsuki: "A Polynomial-Time Algorithm for Checking the Inclusion for Strict Deterministic Restricted One-Counter Automata" IEICE Transactions on Information and Systems. Vol.E78-D(to appear). (1995)

Ken Higuchi、Etsuji Tomita 和 Mitsuo Wakatsuki：“一种用于检查严格确定性限制单计数器自动机包含情况的多项式时间算法”IEICE Transactions on Information and Systems。