Programming Languages and Compilers Commons^™

Mind Change Speed-Up For Learning Languages From Positive Data, Sanjay Jain, Efim Kinber

School of Computer Science & Engineering Faculty Publications

Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes by a learner on all languages with indices not exceeding . For inductive inference of recursive languages, we establish two conditions under which can be made smaller than any recursive unbounded non-decreasing function. We also establish how is affected if at least one of these two conditions does not hold. In the case …

Effective Computer Programming Instruction For Pre-University Albanian Students, Robert Mccloud, Ardiana Sula

School of Computer Science & Engineering Faculty Publications

The relationship between pre-university students and technology is frequently overrated. While we receive glowing reports about how young people are knowledgeable about computers, the truth is that their knowledge is typically about computer content and the manipulation of applications. Young students too often treat the actual programming and understanding of computers as a sort of magical mystery.

In this paper we look at a new Albanian initiative to identify and nurture the most talented of our pre-university students. In particular we look at contributions to the goal of making Albanians the most talented programmers in this area of Europe.

The …

Inductive Inference Of Languages From Samplings, Sanjay Jain, Efim Kinber

School of Computer Science & Engineering Faculty Publications

We introduce, discuss, and study a model for inductive inference from samplings, formalizing an idea of learning different “projections” of languages. One set of our results addresses the problem of finding a uniform learner for all samplings of a language from a certain set when learners for particular samplings are available. Another set of results deals with extending learnability from a large natural set of samplings to larger sets. A number of open problems is formulated.

Variations On U-Shaped Learning, Lorenzo Carlucci, Sanjay Jain, Efim Kinber, Frank Stephen

School of Computer Science & Engineering Faculty Publications

The paper deals with the following problem: is returning to wrong conjectures necessary to achieve full power of algorithmic learning? Returning to wrong conjectures complements the paradigm of U-shaped learning when a learner returns to old correct conjectures. We explore our problem for classical models of learning in the limit from positive data: explanatory learning (when a learner stabilizes in the limit on a correct grammar) and behaviourally correct learning (when a learner stabilizes in the limit on a sequence of correct grammars representing the target concept). In both cases we show that returning to wrong conjectures is necessary to …

Learning Languages From Positive Data And A Finite Number Of Queries, Sanjay Jain, Efim Kinber

School of Computer Science & Engineering Faculty Publications

A computational model for learning languages in the limit from full positive data and a bounded number of queries to the teacher (oracle) is introduced and explored. Equivalence, superset, and subset queries are considered (for the latter one we consider also a variant when the learner tests every conjecture, but the number of negative answers is uniformly bounded). If the answer is negative, the teacher may provide a counterexample. We consider several types of counterexamples: arbitrary, least counterexamples, the ones whose size is bounded by the size of positive data seen so far, and no counterexamples. A number of hierarchies …

On 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 that 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 …

On Learning Of Functions Refutably, Sanjay Jain, Efim Kinber, Rolf Wiehagen, Thomas Zeugmann

School of Computer Science & Engineering Faculty Publications

Learning of recursive functions refutably informally means that for every recursive function, the learning machine has either to learn this function or to refute it, that is to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. Furthermore, all these types are closed under union, though in different strengths. Also, these types are shown to be different with …

Learning Recursive Functions Refutably, Sanjay Jain, Efim Kinber, Rolf Wiehagen, Thomas Zeugmann

School of Computer Science & Engineering Faculty Publications

Learning of recursive functions refutably means that for every recursive function, the learning machine has either to learn this function or to refute it, i.e., to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. All these types are closed under union, though in different strengths. Also, these types are shown to be different with respect to their …

Learning Languages And Functions By Erasing, Sanjay Jain, Efim Kinber, Steffen Lange, Rolf Wiehagen, Thomas Zeugmann

School of Computer Science & Engineering Faculty Publications

Learning by erasing means the process of eliminating potential hypotheses from further consideration thereby converging to the least hypothesis never eliminated. This hypothesis must be a solution to the actual learning problem. The capabilities of learning by erasing are investigated in relation to two factors: the choice of the overall hypothesis space itself and what sets of hypotheses must or may be erased. These learning capabilities are studied for two fundamental kinds of objects to be learned, namely languages and functions. For learning languages by erasing, the case of learning indexed families is investigated. A complete picture of all separations …

Decision Problems Resulting From Grammatical Inference, Sandor Horvath, Efim Kinber, Arto Salomaa, Sheng Yu

School of Computer Science & Engineering Faculty Publications

Grammatical inference is one of the classical areas of language theory.