View Related Documents

Abstract

This paper settles a question about ldquoprudentrdquo ldquovacillatoryrdquo identification of languages. Consider a scenario in which an algorithmic deviceM is presented with all and only the elements of a languageL, andM conjectures a sequence, possibly infinite, of grammars. Three different criteria for success ofM onL have been extensively investigated in formal language learning theory. IfM converges to a single correct grammar forL, then the criterion of success is Gold's seminal notion ofTxtEx-identification. IfM converges to a finite number of correct grammars forL, then the criterion of success is calledTxtFex-identification. Further, ifM, after a finite number of incorrect guesses, outputs only correct grammars forL (possibly infinitely many distinct grammars), then the criterion of success is known asTxtBc-identification. A learning machine is said to beprudent 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 restrictTxtEx-identification, and later Kurtz and Royer showed that prudence does not restrictTxtBc-identification. This paper shows that prudence does not restrictTxtFex-identification.

Fulltext Preview

Image of the first page of the fulltext document