Computer Science
Computer Science
bullet Rowan University IEEE to host international visitors for Sumo Robot Competition | More

bullet Assoc. Prof makes Ironman World Championship, raises funds to fight pancreatic cancer | More

bullet Rowan film project supports White House fight against sexual assault on campus | More

bullet Wanted: Glassboro’s most #RowanPROUD family | More

bullet South Jersey state colleges hit record high enrollment | 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.