Some classes of prolog programs inferable from positive data

Author: M.R.K. Krishna Rao

Source: Theoretical Computer Science Vol. 241, No. 1-2, 2000, 211-234.

Abstract. In this paper, we study inferability of Prolog programs from positive examples alone. The importance of studying inductive inference from positive data alone stems from the scarcity of negative information in practical applications. Starting with Shinohara's result on bounded finite thickness and inductive inference from positive data, we investigate a broad spectrum of classes of Prolog programs inferable from positive data and the relationships between these classes. First we consider programs without local variables and show that a few classes of programs (without any bound on the length of clauses) are inferable from positive data. Then we consider programs with local variables and identify a very useful class of programs inferable from positive data, using mode annotations of predicates and linear predicate inequalities.

©Copyright 2000 Elsevier Science