Elementary Formal System as a Unifying Framework for Language Learning

Abstract

This paper presents a unifying framework for language learning, especially for inductive inference of various classes of languages. The elementary formal systems (EFS for short), Smullyan invented to develop his recursive function theory, are proved suitable to generate languages. In this paper we first point out that EFS can also work as a logic programming language, and the resolution procedure for EFS can be used to accept languages. We give a theoretical foundation to EFS from the viewpoint of semantics of logic programs. Hence, Shapiro's theory of model inference can naturally be applied to our language learning by EFS. We introduce some subclasses of EFS's which correspond to Chomsky hierarchy and other important classes of languages. We discuss computations of unifiers between two terms. Then we give, in a uniform way, inductive inference algorithms including refinement operators for these subclasses and show their completeness. This paper was supported by Grant-in-Aid for Scientific Research on Priority Areas (No.63633011), The Ministry of Education, Science and Culture of Japan.