Learning elementary formal system

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 with correspond to Chomsky hierarchy and other important classes of languages. We discuss computations of unifiers between two terms. Then we give inductive inference algorithms including refinement operators for these subclasses and show their completeness.

Authors

• Setsuo Arikawa
• Takeshi Shinohara
• Akihiro Yamamoto

Keywords

No keywords are indexed for this paper.