New Year for Rowan students takes them to Third World countries to volunteer | More

Visiting Fulbright Scholars Aim to Make Computers Talk | More

Prof. Jooh Lee Honored with Campbell Endowed Chair | More

Cooper Medical School of Rowan University and Coriell Institute for Medical Research Build Educational Alliance | More


The latest version of CLAS notes is available for download in the newsletters section.

Title
Synthesizing Enumeration Techniques for Language Learning

Authors
Ganesh Baliga
Department of Computer Science
Rowan College of New Jersey
Glassboro, NJ 08028

John Case
Department of Computer and Information Sciences
University of Delaware
Newark, DE 19716

Sanjay Jain
Information Systems and Computer Science department
National University of Singapore
Singapore

Abstract

In the context of learning programs in the limit for functions, a variety of enumeration techniques are important and ubiquitous. Here is the archetypal case. Suppose one has an recursively enumerable set
of programs for computing total functions. One proceeds as follows. At each point one is given finitely much data about an input function, one conjectures the first program, if any, listed in P that is correct on that data. Clearly for functions f computed by some program in P, this procedure will eventually lock onto a fixed conjecture correct for f. We consider the same technique as might be applied to language learning.

The present paper was inspired by the following amazingly negative result due to Osherson, Stob and Weinstein. They show: there is no algorithm for translating any pair of grammars (g,g') into a learning procedure which, from positive data about any one of the languages generated by g and g', finds in the limit, for this language, a correct grammar! In this paper we seek to assuage this negative result by loosening the requirements of successful learning. We consider the limiting synthesis of learning machines for learnable recursively enumerable classes of languages. One of the results in this paper is a
characterization of uniformly decidable classes in terms of some conditions due to Dana Angluin.