INDUCTIVE INFERENCE OF FORMAL LANGUAGES

概要

論文の詳細を見る
This paper develops a mathematical theory of language identification from a set theoretic viewpoint. We investigate two types of language classes called M-finite thickness and finite elasticity as a hypothesis space of an inductive inference machine. It is known that both of the families of such classes include interesting and important classes and are substantially large. For a class with M-finite thickness, we first show some equivalences between several key concepts in language identification such as a finite tell-tale and others. We also show that M-finite thickness is preserved under some operations such as intersection, concatenation and so on as well as finite elasticity, except union operation. Then we apply those results to problems of inferability in the criteria of ordinary identification in the limit or inductive refutable identification proposed by Mukouchi and Arikawa as a framework for machine discovery. In particular, we present a characterization theorem and some useful sufficient conditions for inductive refutable inferability from complete data, in case a hypothesis space has M-finite thickness. Furthermore, we discuss inductive inference of length-bounded elementary formal systems as a framework for defining target languages.
Research Association of Statistical Sciencesの論文
1995-03-00