Open problems in “systems that learn”

摘要

In this paper we solve some of the open problems in D. Osherson, M. Stob, 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 languages that can be identified on “noisy” text (i.e., a text which may contain some elements which are not in the language being learned) strictly contains the collection of classes of languages that can be identified on “imperfect” text (i.e., a text which may contain some extra elements and may leave out some elements from the language being learned). We also show that memory limited identification is strictly more restrictive that memory bounded identification. Besides solving the above two open problems from op. cit., we also give partial solutions to other open problems in ibid.