Congratulations Graduates 2013! | More

Regional high school students can RISE in Rowan Engineering | More

College of Engineering welcomes middle school girls to annual AWE summer workshops | More

Rowan sets information session for Young Profs Exploration Camp | More

Cancer survivor turns dream into reality | More

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.