OPEN PROBLEMS IN SYSTEMS THAT LEARN

In this paper we solve some of the open problems in D. Osherson, M. St ob, and S. Weinstein (''Systems That Learn,'' MIT Press, Cambridge, MA , 1986). We also give partial solutions to some other open problems in the book. In particular we show that the collection of classes of lan guages that can be identified on ''noisy'' text (i.e., a text which ma y contain some elements which are not in the language being learned) s trictly contains the collection of classes of languages that can be id entified on ''imperfect'' text (i.e., a text which may contain some ex tra elements and may leave out some elements from the language being l earned). We also show that memory limited identification is strictly m ore restrictive that memory bounded identification. Besides solving th e above two open problems from op. cit., we also give partial solution s to other open problems in ibid. (C) 1994 Academic Press, Inc.