Computer Science
Computer Science
bullet Rowan announces inaugural Excellence in Diversity awards | More

bullet Rowan University students present cutting-edge research at the 17th Annual STEM Student Research Symposium | More

bullet “Fly Me to the Moons!” plays at Edelman Planetarium | More

bullet The Princeton Review names Rowan to 2014 "Green Guide" | More

bullet At Rowan Graduate Commencement: Levine to speak to graduates; Bartolozzi to receive honorary degree | More

Technical Report Number TR1996-1

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.