Prudence in Vacillatory Language Identification (Extended Abstract)

Abstract

The present paper settles an open question about ‘prudent’ vacillatory identification of grammars from positive data only. Consider a scenario in which a learner M is learning a language L from positive data. Three different criteria for success of M on L have been investigated in formal language learning theory. If M converges to a single correct grammar for L , then the criterion of success is Gold's seminal notion of TxtEx-identification. If M converges to a finite number of correct grammars for L , then the criterion of success is called TxtFex-identification. And, if M, after a finite number of incorrect guesses, outputs only correct grammars for L (possibly infinitely many distinct grammars), then the criterion of success is known as TxtBc-identification. A learner is said to be prudent according to a particular criterion of success just in case the only grammars it ever conjectures are for languages that it can learn according to that criterion. This notion was introduced by Osherson, Stob, and Weinstein with a view to investigate certain proposals for characterizing natural languages in linguistic theory. Fulk showed that prudence does not restrict TxtEx-identification, and later Kurtz and Royer were able to show that prudence does not restrict TxtBc-identification. The present paper settles this question by showing that prudence does not restrict TxtFex-identification.