Open problems in "systems that learn"

Mark Fulk, Sanjay Jain, Daniel N. Osherson

Research output: Contribution to journalArticle

34 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)589-604
Number of pages16
JournalJournal of Computer and System Sciences
Volume49
Issue number3
DOIs
StatePublished - Dec 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Open problems in "systems that learn"'. Together they form a unique fingerprint.

  • Cite this