Abstract
A formal system is a finite set of expressions, such as a grammar or a Prolog program. A semantic mapping from formal systems to concepts is said to be monotonic if it maps larger formal systems to larger concepts. A formal system Γ is said to be reduced with respect to a finite setX if the concept defined by Γ containsX but the concepts defined by any proper subset Γ′ of Γ cannot contain some part ofX. Assume a semantic mapping is monotonic and formal systems consisting of at mostn expressions that are reduced with respect toX can define only finitely many concepts for any finite setX and anyn. Then, the class of concepts defined by formal systems consisting of at mostn expressions is shown to be inferable from positive data. As corollaries, the class of languages defined by length-bounded elementary formal systems consisting of at most,n axioms, the class of languages generated by context-sensitive grammars consisting of at mostn productions, and the class of minimal models of linear Prolog programs consisting of at mostn definite clauses are all shown to be inferable from positive data.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Angluin, D.: Finding common patterns to a set of strings, Proc 11th Annual ACM Symp. Theory of Computing, 130–141, 1979.
Angluin, D.: Inductive inference of formal languages from positive data, Inform. Contr.,45, 117–135, 1980.
Angluin, D. and Smith, C. H.: Inductive inference: Theory and methods, Computing Surveys,15, 237–269, 1983.
Arikawa, S.: Elementary formal systems and formal languages — Simple formal systems, Memoirs of Fac. Sci., Kyushu Univ. Ser. A, Math.,24, 47–75, 1970.
Arikawa, S., Shinohara, T. and Yamamoto, A.: Elementary formal system as a unifying framework for language learning, Proc. 2nd Workshop Comput. Learning Theory, 312–327, 1989.
Arimura, H.: Completeness of depth-bounded resolution in logic programming, Proc. 6th Conf, Japan Soc. Software Sci. Tech., 61–64, 1989.
Gold, E.M.: Language identification in the limit, Inf. & Contr.,10, 447–474, 1967.
Lloyd, J.W.:Foundations of Logic Programming Springer-Verlag, 1984.
Motoki, T. and Shinohara, T.: Correct definition of finite elasticity, Technical Report RIFIS-TR-CS-29, Kyushu University, 1990.
Shapiro, E.Y.: Inductive inference of theories from facts, YALEU/DCS/TR-192, 1981.
Shapiro, E.Y.: Alternation and the computational complexity of logic programs. J. Logic Program.,1, 19–33, 1984.
Shinohara, T.: Polynomial time inference of extended regular pattern languages, LNCS,147, 115–127, 1983.
Shinohara, T.: Inferring unions of two pattern languages, Bull. Inf. Cybern.,20, 83–88, 1983.
Shinohara, T.: Inductive inference of formal systems from positive data, Bull. Inf. Cybern.,22, 9–18, 1986.
Shinohara, T.: Inductive inference from positive data is powerful, Technical Report RIFIS-TR-CS-20, Kyushu University, 1989.
Smullyan, R. M.:Theory of Formal Systems, Princeton Univ. Press, 1961.
Wright, K.: Identification of unions of languages drawn from an identifiable class, Proc. 2nd Workshop Comput. Learning Theory, 328–333, 1989.
Yamamoto, A.: Elementary formal system as a logic programming language, Proc. Logic Program. Conf. ’89, ICOT, 123–132, 1989.
Author information
Authors and Affiliations
About this article
Cite this article
Shinohara, T. Inductive inference of monotonic formal systems from positive data. NGCO 8, 371–384 (1991). https://doi.org/10.1007/BF03037094
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF03037094