权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Developments of LearningAlgorithms for Deterministic Context-Free Languages in Some Classes and Their Applications

某些类别的确定性上下文无关语言学习算法的进展及其应用

基本信息

批准号：
18500108
负责人：
WAKATSUKI Mitsuo
金额：
$ 0.86万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

项目摘要

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.

机器学习是实现人工智能的重要研究领域之一，计算学习理论是从数学上分析机器学习可能性的一种范式。在形式语言理论中，确定性上下文无关语言类在实际应用中很重要。在本研究中，我们关注的是接受确定性上下文无关语言的确定性下推自动机（简称dpda）的一些子类和相应的形式文法子类。本研究的目的是发展dpda's子类别的学习演算法，并将这些演算法应用于实际问题，我们有以下的研究成果。开发学习算法的基础：我们提出了一种简单而直接的算法，用于检查某对非实时确定性下推传感器（简称dpdt）的等效性，其中dpdt是通过将输出函数附加到dpda来获得的。此外，我们已经给出了一个多项式时间算法，用于检查实时严格确定性限制单计数器传感器的等效性，这是实时dpdt的，只有一个堆栈符号。我们知道等价性检验算法在自动机和形式文法的学习系统中起着重要的作用。这些结果可用于对dpdt的某些子类进行查询学习。学习算法的发展：我们已经提出了一个统一的识别算法的限制，从积极的数据的扩展类定义的一类语言的基础上，一类有限子集的字符串。此外，我们已经证明了一个子类的dpda的称为Szilard严格确定性限制一计数器自动机和有限状态转换器的某个子类是多项式时间可识别的限制从积极的数据。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A unified algorithn for extending classes of languages identifiable in the limit from positive data

一种统一的算法，用于扩展可在有限的正数据中识别的语言类别

DOI：
发表时间：
2006
期刊：
影响因子：
0
作者：
Mitsuo Wakatsuki;Etsuji Tomita and Go Yamada
通讯作者：
Etsuji Tomita and Go Yamada

「研究成果報告書概要(和文)」より

摘自《研究结果报告摘要（日文）》

DOI：
发表时间：
2005
期刊：
影响因子：
0
作者：
Kawauchi;et. al.;Nishimura et al.;Dezawa et al.;Yoshizawa et al.;星野幹雄;星野幹雄
通讯作者：
星野幹雄

A unified algorithm for extending classes of languages identifiable in the limit from positive data

一种统一的算法，用于扩展可在有限的正数据中识别的语言类别

DOI：
发表时间：
2006
期刊：
Lecture Notes in Artificial Intelligence 4201
影响因子：
0
作者：
M.Wakatsuki;E.Tomita;G.Yamada
通讯作者：
G.Yamada

A polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers

一种用于检查实时严格确定性受限单计数器传感器等价性的多项式时间算法

DOI：
发表时间：
2008
期刊：
The IEICE Transactions on Information and Systems (Japanese Edition) J91-D 5)
影响因子：
0
作者：
Kazushi;Seino;Etsuji;Tomita;Mitsuo;Wakatsuki
通讯作者：
Wakatsuki

ε-推移を許したある決定性プッシュダウン変換器対の等価性判定

一对允许 ε 跃迁的确定性下推转换器的等价确定