Mitsuo WAKATSUKI (若月 光夫)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
We have developed a polynomial-time algorithm for checking the equivalence of deterministic restricted one-counter transducers (DROCT's for short), which are deterministic pushdown transducers having just one stack symbol, that accept by final state with possible epsilon-moves. By extending this technique, we have also developed a polynomial-time algorithm for checking the inclusion of these DROCT's. Then, we have presented a polynomial-time algorithm for learning real-time DROCT's which accept by final state via membership and equivalence queries. Furthermore, we have shown that the regularity of the behavior of some programs for playing games of Daihinmin, which is one of card games, on computers can be extracted by using the EUREKA system which incorporated an identification algorithm of the class of k-reversible languages, which is a subclass of regular languages, for analyzing songs of the Bengalese finch.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: 1050000)
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.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1200000, indirect: 150000)
The machine learning is one of the most important research fields for the realization of the artificial intelligence, and the computational learning theory is a paradigm which analyzes mathematically about the possibility for the machine learning. In formal language theory, the class of deterministic context-free languages is important in practical use. In this research, we are concerned with some subclasses of deterministic pushdown automata (dpda's for short) which accept deterministic context-free languages and the corresponding subclasses of formal grammars. The aim of this research is to develop learning algorithms for subclasses of dpda's and to apply these algorithms to practical problems.
We had the following research results.
1. Basics to develop learning algorithms: We have proposed a simple and direct algorithm for checking the equivalence of a certain pair of non-real-time deterministic pushdown transducers (dpdt's for short), where dpdt's are obtained by attaching the output function to dpda's. In addition, we have given a polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers, which are real-time dpdt's that have just one stack symbol. We know that the equivalence checking algorithm plays an important role in learning systems which are formulated as automata and formal grammars. These results can be used for learning via queries for some subclasses of dpdt's.
2. Developments of learning algorithms: We have presented a unified identification algorithm in the limit from positive data for the extended class defined by a class of languages to be based on and a class of finite subsets of strings. Furthermore, we have proved that a subclass of dpda's called Szilard strict deterministic restricted one-counter automata and a certain subclass of finite state transducers are polynomial time identifiable in the limit from positive data.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3400000, indirect: -)
The information binding in human brain is getting important to explain and to understand how human being can recognize the outer world so easily. Besides this, we expect that applying the binding mechanism to recognizer, we can get much better recognition performance. In this research we developed the neural networks that can well explain the information binding in the human brain. Based on the fact that the previous neural models are difficult to represent the spike synchronization or asynchronization, we developed two phasor neural models. One is the phase-rate oscillating neural model, in which the phase represents the sinusoidal phase. The other is covariance neural model, in which the cosine of the phase difference between two neurons represents the covariance coefficient. In both model we implemented the Hebb learning and Boltzmann learning rules to get the efficient learning. From the computer simulation results, we showed that the proposed learning rules work much more efficient than ordinal models. Applying the knowledge obtained from these models, we proposed the brain wave recognizer which shows much higher performance than previous. We also developed the theory of generalization in learning.

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