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

点击翻译按钮获取中文摘要

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.