Physical Sciences and Mathematics Commons^™

Learning Languages From Positive Data And A Limited Number Of Short Counterexamples, Sanjay Jain, Efim Kinber

School of Computer Science & Engineering Faculty Publications

We consider two variants of a model for learning languages in the limit from positive data and a limited number of short negative counterexamples (counterexamples are considered to be short if they are smaller than the largest element of input seen so far). Negative counterexamples to a conjecture are examples which belong to the conjectured language but do not belong to the input language. Within this framework, we explore how/when learners using n short (arbitrary) negative counterexamples can be simulated (or simulate) using least short counterexamples or just ‘no’ answers from a teacher. We also study how a limited number …