| Creator |
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| 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 la...rger 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.show more
|
Export Mendeley
rifis-tr-29