INDUCTIVE INFERENCE FROM NEGATIVE DATA
Takeshi Shinohara · Bulletin of informatics and cybernetics · 1985
Inductive inference of a language L from negative data is the one based only on words not in L. In other words it is the inference of the complement Lc from positive data. This paper describes the relation between inferability from positive data and that from negative data. It is not the case that the inferability of a class of languages always guarantees the inferability from negative data. Some non trivial classes are inferable both from positive data and from negative data. 1. Preliminaries We start with a brief review of inductive inference from positive data according to Angluin [1, 2]. Let 2 ' be a finite alphabet of symbols. The set of all finite strings over I is denoted by X. A language is a subset of I*. DEFINITION 1. A class of lanuages..0=L1i L2, •• • is said to be an indexed family of recursive languages if there exists a computable function f such that 1, if x is in Li; f(i, x)= 0, otherwise. From here on, the classes of languages are assumed to be indexed families of recursive languages. DEFINITION 2. A positive presentation of a nonempty language L is an infinite sequence s = s1, s2, such that the set of all strings in s is equal to L. DEFINITION 3. A negative presentation of a language L not equal to I * is an in finite sequence s = s1i s2, • • • such that the set of all strings in s is euqal to the com plement s'* — L. DEFINITION 4. Inference machine M is an effective procedure that requests input from time to time and produces output from time to time. AI on input sequence s=s1, s2, • converges to go iff the sequence of outputs g=g1, g2, produced by M when elements in s are successively given to M is either a finite sequence ending with go or an infinite sequence such that all but finitely many elements in g are equal to go. DEFINITION 5. A class of languages oC=L1i L2, •• • is said to be inferable from positive data (inferable from negative data) if there exits an inference machine M such