Prudence in vacillatory language identification

Abstract

This paper settles a question about "prudent" "vacillatory" identification of languages. Consider a scenario in which an algorithmic device M is presented with all and only the elements of a language L, and M conjectures a sequence, possibly infinite, of grammars. Three different criteria for success of M on L have been extensively 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. Further, 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 learning machine 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 investigating certain proposals for characterizing natural languages in linguistic theory. Fulk showed that prudence does not restrict TxtEx-identification, and later Kurtz and Royer showed that prudence does not restrict TxtBc-identification. This paper shows that prudence does not restrict TxtFex-identification. © 1995 Springer-Verlag New York Inc.