Inductive Inference of Monotonic Formal Systems from Positive Data

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 $ Gamma $ is said to be reduced with respect to a finite set X if the concept defined by $ Gamma $ contains X but the concepts defined by any proper subset $ Gamma $ of $ Gamma $ cannot contain some part of X. Assume a semantic mapping is monotonic and formal systems consisting of at most n expressions that are reduced with respect to X can define only finitely many concepts for any finite set X and any n. Then, the class of concepts defined by formal systems consisting of at most n 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 most n productions, and the class of minimal models of linear Prolog programs consisting of at most n definite clauses are all shown to be inferable from positive data.